Optimality of the Johnson-Lindenstrauss lemma

摘要

For any d,n > 2 and l/(min{n,d})~(0.4999) < ε < 1, we show the existence of a set of n vectors X c R~d such that any embedding f : X →R~m satisfying {formula} must have {formula} This lower bound matches the upper bound given by the Johnson-Lindenstrauss lemma [JL84]. Furthermore, our lower bound holds for nearly the full range of e of interest, since there is always an isometric embedding into dimension min{d, n} (either the identity map, or projection onto span(X)). Previously such a lower bound was only known to hold against linear maps f, and not for such a wide range of parameters ε,n,d [LN16]. The best previously known lower bound for general f was m = (ε~(-2)lgn/lg(1/ε)) [Wel74], [A1o03], which is suboptimal for any ε = o(1).