Optimality of the Johnson-Lindenstrauss Lemma
Kasper Green Larsen, Jelani Nelson · 2017
For any d, n ≥ 2 and 1/(min{n, d})0.4999dsuch that any embedding f : X → ℝmsatisfying ∀x, y ∈ X, (1-ε)∥x-y∥22≤ ∥f(x)-f(y)∥22≤ (1+ε)∥x-y∥22must have m = Ω(ε-2lg n). 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 ε 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 = Ω(ε-2lg n/ lg(1/ε)) [Wel74], [Alo03], which is suboptimal for any ε = o(1).