Optimality of the Johnson-Lindenstrauss Lemma

For any integers $d,n\ge 2$ and $1/({\min{n,d}})^{0.4999} < \varepsilon<1$,weshowtheexistenceofasetof$n$vectors$X\subset $\mathbb{R}$^d$suchthatanyembedding$f:X\rightarrow $\mathbb{R}$^m$satisfying$$ \forall x,y\in X,\ (1-\varepsilon)|x-y|_2^2\le |f(x)-f(y)|_2^2 \le (1+\varepsilon)|x-y|_2^2 $$musthave$$ m = \Omega(\varepsilon^{-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 $(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(\varepsilon^{-2}\lg n/\lg(1/\varepsilon))$ [Wel74, Lev83, Alo03], which is suboptimal for any $\epsilon =o(1)$.