Optimality of the Johnson-Lindenstrauss Lemma

Abstract

For any integers $d,n\ge 2$ and $1/(\min \{n,d\}{)}^{0.4999}<\epsilon <1$, we show the existence of a set of $n$ vectors $X\subset {\mathbb{R}}^d$ such that any embedding $f:X\to {\mathbb{R}}^m$ satisfying $$\forall x,y\in X,(1-\epsilon )\Vert x-y{\Vert }_2^2\le \Vert f(x)-f(y){\Vert }_2^2\le (1+\epsilon )\Vert x-y{\Vert }_2^2$$ must have $$m=\Omega ({\epsilon }^{-2}\lg 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 $\epsilon$ of interest, since there is always an isometric embedding into dimension $\min \{d,n\}$ (either the identity map, or projection onto $\mathrm{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 $\epsilon ,n,d$ [LN16]. The best previously known lower bound for general $f$ was $m=\Omega ({\epsilon }^{-2}\lg n/\lg (1/\epsilon ))$ [Wel74, Lev83, Alo03], which is suboptimal for any $\epsilon =o(1)$.

v2: simplified proof, also added reference to Lev83