The Johnson-Lindenstrauss Lemma Is Optimal for Linear Dimensionality Reduction

Abstract

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^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.