2024/03/06 by Rafael Chiclana, Chiclana, Rafael, Mark Iwen +3
Computer Science · Mathematics · #51F30 #65D18 #68R12 #Advanced Banach Space Theory #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Mathematical Analysis and Transform Methods #Metric Geometry (math.MG) #Numerical Analysis (math.NA) #Optimization and Variational Analysis
paper · pdf · doi:10.48550/arxiv.2403.03969
openalex publication_date 2024/03/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The celebrated Johnson-Lindenstrauss lemma states that for all ε ∈ (0,1) and finite sets X ⊆ ℝN with n>1 elements, there exists a matrix Φ∈ ℝm × N with m=O(ε-2log n) such that (1 - ε) ‖x-y‖2 ≤ ‖Φx-Φy‖2 ≤ (1+ε)‖ x- y‖2 ∀ x, y ∈ X. Herein we consider terminal embedding results which have recently been introduced in the computer science literature as stronger extensions of the Johnson-Lindenstrauss lemma for finite sets. After a short survey of this relatively recent line of work, we extend the theory of terminal embeddings to hold for arbitrary (e.g., infinite) subsets X ⊆ ℝN, and then specialize our generalized results to the case where X is a low-dimensional compact submanifold of ℝN. In particular, we prove the following generalization of the Johnson-Lindenstrauss lemma: For all ε ∈ (0,1) and X⊆ℝN, there exists a terminal embedding f: ℝN \longrightarrow ℝm such that (1 - ε) ‖ x - y ‖2 ≤ ‖ f(x) - f(y) ‖2 ≤ (1 + ε) ‖ x - y ‖2 ∀ x ∈ X ~\rm and~ ∀ y ∈ ℝN. Crucially, we show that the dimension m of the range of f above is optimal up to multiplicative constants, satisfying m=O(ε-2 ω2(SX)), where ω(SX) is the Gaussian width of the set of unit secants of X, SX=\(x-y)/‖x-y‖2 \colon x ≠ y ∈ X\. Furthermore, our proofs are constructive and yield algorithms for computing a general class of terminal embeddings f, an instance of which is demonstrated herein to allow for more accurate compressive nearest neighbor classification than standard linear Johnson-Lindenstrauss embeddings do in practice.