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(ε−2logn) 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(ε−4logn). Our proof is via a tighter analysis of (a specific instantiation of) the embedding recipe of Mahabadi et al.