The Johnson-Lindenstrauss lemma is optimal for linear dimensionality reduction

DOI10.4230/LIPICS.ICALP.2016.82MaRDI QIDQ4598222zbMATH OpenOpenAlexFDO

Authors Kasper Green Larsen, Jelani Nelson

Publication date 19 December 2017

Full work available at URL https://arxiv.org/abs/1411.2404

zbMATH Keywords

dimensionality reductionJohnson-Lindenstrauss lemmalower bounds

Mathematics Subject Classification ID

Local theory of Banach spaces (46B07)

Abstract: For any $n>1$ and $0<varepsilon<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,el{l}_2)$ to $el{l}_2^m$ with distortion at most $1+varepsilon$ must have $m=Omega(minn,varepsilo{n}^{-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/varepsilon)$ factor.

Recommendations

• Optimal terminal dimensionality reduction in Euclidean space
• Almost Optimal Explicit Johnson-Lindenstrauss Families
• Sparsity lower bounds for dimensionality reducing maps
• An elementary proof of a theorem of Johnson and Lindenstrauss
• Optimal bounds for Johnson-Lindenstrauss transformations

Cited in

(21)

• Moments of Gaussian chaoses in Banach spaces
• Paraunitary matrices, entropy, algebraic condition number and Fourier computation
• Binary vectors for fast distance and similarity estimation
• Almost Optimal Explicit Johnson-Lindenstrauss Families
• On binary embedding using circulant matrices
• Fast cross-polytope locality-sensitive hashing
• Real-valued embeddings and sketches for fast distance and similarity estimation
• On using Toeplitz and circulant matrices for Johnson-Lindenstrauss transforms
• Dimensionality reduction with subgaussian matrices: a unified theory
• Persistent homology for low-complexity models
• Optimal terminal dimensionality reduction in Euclidean space
• Simple analyses of the sparse Johnson-Lindenstrauss transform
• Optimal bounds for Johnson-Lindenstrauss transforms and streaming problems with sub-constant error
• One-bit sensing, discrepancy and Stolarsky's principle
• Sparsity lower bounds for dimensionality reducing maps
• Lower bounds on the low-distortion embedding dimension of submanifolds of \(\mathbb{R}^n\)
• scientific article; zbMATH DE number 7758314 (Why is no real title available?)
• Optimality of the Johnson-Lindenstrauss dimensionality reduction for practical measures
• Improved linear embeddings via Lagrange duality
• Randomly projected convex clustering model: motivation, realization, and cluster recovery guarantees
• Random projections for curves in high dimensions

This page was built for publication: The Johnson-Lindenstrauss lemma is optimal for linear dimensionality reduction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4598222)