The Johnson-Lindenstrauss lemma is optimal for linear dimensionality reduction

Kasper Green Larsen, Jelani Nelson

For any $n>1$ and $0<\epsilon <1/2$, we show the existence of an $n^{O(1)}$-point subset $X$ of ${\mathbb{R}}^n$ such that any linear map from $(X,{\ell }_2)$ to ${\ell }_2^m$ with disto…