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 }_2^m$ with distortion at most $1+\epsilon$ must have $m=\Omega (\min \{n,{\epsilon }^{-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/\epsilon )$ factor.

Cited by in corpus (9)

• On the Complexity of Inner Product Similarity Join
• Bolt: Accelerated Data Mining with Fast Vector Compression
• Embeddings of Schatten Norms with Applications to Data Streams
• Toward a unified theory of sparse dimensionality reduction in Euclidean space
• Moments of Gaussian chaoses in Banach spaces
• Relative Error Embeddings for the Gaussian Kernel Distance
• Linear Dimensionality Reduction in Linear Time: Johnson-Lindenstrauss-type Guarantees for Random Subspace
• Nonlinear Dimension Reduction via Outer Bi-Lipschitz Extensions
• Fast Nearest Neighbor Preserving Embeddings