The Johnson-Lindenstrauss lemma is optimal for linear dimensionality reduction

For any $n>1$ and $0<\epsilon <1\mathrm{/}2$, we show the existence of an $n^{O(1)}$-point subset $X$ of ${\mathbb{R}}^n$ such that any linear map from $(X,{\mathrm{\ell }}_2)$ to ${\mathrm{\ell }}_2^m$ with distortion at most $1+\epsilon$ must have $m = \Omega(\min{n, \varepsilon^{-2}\log n})$. Our lower bound matches the upper bounds provided by the identity matrix and the Johnson-Lindenstrauss lemma, improving the previous lower bound of Alon by a $\log (1\mathrm{/}\epsilon )$ factor.