Optimal terminal dimensionality reduction in Euclidean space

Let varepsilon∈(0,1) and Xsubsetmathbb Rd be arbitrary with |X| having size n>1. The Johnson-Lindenstrauss lemma states there exists f:Xrightarrowmathbb Rm with m = O(varepsilon-2log n) such that forall x∈ X forall y∈ X, |x-y|2 ≤ |f(x)-f(y)|2 ≤ (1+varepsilon)|x-y|2 . We show that a strictly stronger version of this statement holds, answering one of the main open questions of [MMMR18]: "forall y∈ X" in the above statement may be replaced with "forall y∈mathbb Rd", 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(varepsilon-4log n). Our proof is via a tighter analysis of (a specific instantiation of) the embedding recipe of [MMMR18].