This is an announcement for the paper “Optimality of the Johnson-Lindenstrauss Lemma” by Kasper Green Larsenhttps://arxiv.org/find/cs/1/au:+Larsen_K/0/1/0/all/0/1, Jelani Nelsonhttps://arxiv.org/find/cs/1/au:+Nelson_J/0/1/0/all/0/1.
Abstract: For any integers $d, n \geq 2$ and $1/({\min{n,d}})^{0.4999} <\eps<1$, we show the existence of a set of $n$ vectors $X\subset \R^d$ such that any embedding $f:X\rightarrow \R^m$ satisfying $$\forall x,y\in X,\ (1-\eps)|x-y|_2^2\le |f(x)-f(y)|_2^2 \le (1+\eps)|x-y|_2^2$$ must have $$m = \Omega(\eps^{-2} \lg n).$$ This lower bound matches the upper bound given by the Johnson-Lindenstrauss lemma \cite{JL84}. Furthermore, our lower bound holds for nearly the full range of $\eps$ of interest, since there is always an isometric embedding into dimension $\min{d, n}$ (either the identity map, or projection onto $\mathop{span}(X)$).
Previously such a lower bound was only known to hold against {\em linear} maps $f$, and not for such a wide range of parameters $\eps, n, d$ \cite{LarsenN16}. The best previously known lower bound for general $f$ was $m = \Omega(\eps^{-2}\lg n/\lg(1/\eps))$ \cite{Welch74,Alon03}, which is suboptimal for any $\eps = o(1)$.
The paper may be downloaded from the archive by web browser from URL https://arxiv.org/abs/1609.02094