Optimality of the Johnson-Lindenstrauss Lemma

2016/09/07 by Larsen, Kasper Green, Nelson, Jelani · 7 citations
#Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Functional Analysis (math.FA) #Information Theory (cs.IT)

paper · doi:10.48550/arxiv.1609.02094

Abstract

For any integers d, n ≥ 2 and 1/(min\n,d\)^0.4999 < ε<1, we show the existence of a set of n vectors X⊂ ℝ^d such that any embedding f:X→ ℝ^m satisfying ∀ x,y∈ X, (1-ε)‖x-y‖₂²≤ ‖f(x)-f(y)‖₂² ≤ (1+ε)‖x-y‖₂² must have m = Ω(ε^-2 \lg n). This lower bound matches the upper bound given by the Johnson-Lindenstrauss lemma [JL84]. Furthermore, our lower bound holds for nearly the full range of ε of interest, since there is always an isometric embedding into dimension min\d, n\ (either the identity map, or projection onto \mathopspan(X)). Previously such a lower bound was only known to hold against linear maps f, and not for such a wide range of parameters ε, n, d [LN16]. The best previously known lower bound for general f was m = Ω(ε^-2\lg n/\lg(1/ε)) [Wel74, Lev83, Alo03], which is suboptimal for any ε = o(1).

Cited by

• Quantization for Vector Search under Streaming Updates
• An Exploratory Study of Bayesian Prompt Optimization for Test-Driven Code Generation with Large Language Models
• Fast Dimensionality Reduction from ℓ₂ to ℓ_p
• Johnson-Lindenstrauss Lemma Beyond Euclidean Geometry
• Linear Causal Representation Learning by Topological Ordering, Pruning, and Disentanglement
• Balancing Utility and Privacy: Dynamically Private SGD with Random Projection
• Dimension Reduction for Clustering: The Curious Case of Discrete Centers
• Compressibility Barriers to Neighborhood-Preserving Data Visualizations

Related

• The Johnson-Lindenstrauss lemma is optimal for linear dimensionality reduction
• Optimal terminal dimensionality reduction in Euclidean space
• On Using Toeplitz and Circulant Matrices for Johnson-Lindenstrauss Transforms
• On Outer Bi-Lipschitz Extensions of Linear Johnson-Lindenstrauss Embeddings of Subsets of ℝ^N
• Optimal Bounds for Johnson-Lindenstrauss Transformations