On Outer Bi-Lipschitz Extensions of Linear Johnson-Lindenstrauss Embeddings of Subsets of RN

The celebrated Johnson-Lindenstrauss lemma states that for all ε ∈ (0,1) and finite sets X ⊆ RN with $n>1$ elements, there exists a matrix Φ ∈ Rm × N with m=O(ε⁻²log 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 ⊆ RN, and then specialize our generalized results to the case where X is a low-dimensional compact submanifold of RN. In particular, we prove the following generalization of the Johnson-Lindenstrauss lemma: For all ε ∈ (0,1) and XN, there exists a terminal embedding f: RN Rᵐ such that (1 - ε) \| x - y \|₂ ≤ \| f(x) - f(y) \|₂ ≤ (1 + ε) \| x - y \|₂ ∀ \, x ∈ X ~ and~ ∀ \, y ∈ RN. Crucially, we show that the dimension m of the range of f above is optimal up to multiplicative constants, satisfying m=O(ε⁻² ω²(SX)), where ω(SX) is the Gaussian width of the set of unit secants of X, SX=\(x-y)/\|x-y\|₂ 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.