Optimal terminal dimensionality reduction in Euclidean space

Let ε∈(0,1) and X ⊂ d be arbitrary with | X | having size n >1. The Johnson-Lindenstrauss lemma states there exists f : X → m with m = O (ε −2 log n ) such that ∀ x ∈ X ∀ y ∈ X , || x − y || 2 ≤ || f ( x )− f ( y )|| 2 ≤ (1+ε)|| x − y || 2 . We show that a strictly stronger version of this statement holds, answering one of the main open questions posed by Mahabadi et al. in STOC 2018: “∀ y ∈ X ” in the above statement may be replaced with “∀ y ∈ d ”, so that f not only preserves distances within X , but also distances to X from the rest of space. Previously this stronger version was only known with the worse bound m = O (ε −4 log n ). Our proof is via a tighter analysis of (a specific instantiation of) the embedding recipe of Mahabadi et al.

Authors

• Shyam Narayanan
• Jelani Nelson

Keywords

• dimension reduction
• random projections
• terminal embeddings