Larsen, Kasper GreenNelson, Jelani2015-07-152014Larsen, Kasper Green, and Jelani Nelson. 2014. The Johnson-Lindenstrauss Lemma Is Optimal for Linear Dimensionality Reduction. Working Paper (November 10).http://nrs.harvard.edu/urn-3:HUL.InstRepos:17369243For 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^m_2\) with distortion at most \(1+\epsilon\) must have \(m=\Omega(min \{n,\epsilon^{−2}logn\})\). 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/\epsilon)\) factor.en-USResearch Paper or Report2015-01-13Kasper Green Larsen, Jelani Nelson2015-07-15