Optimal terminal dimensionality reduction in Euclidean space

Let $\epsilon \in (0,1)$ and $X\subset {\mathbb{R}}^d$ be arbitrary with $\mathrm{\mid }X\mathrm{\mid }$ having size $n>1$. The Johnson-Lindenstrauss lemma states there exists $f:X\to {\mathbb{R}}^m$ with $m=O({\epsilon }^{-2}\log n)$ such that $$\mathrm{\forall }x\in X\mathrm{\forall }y\in X,\mathrm{\parallel }x-y{\mathrm{\parallel }}_2\le \mathrm{\parallel }f(x)-f(y){\mathrm{\parallel }}_2\le (1+\epsilon )\mathrm{\parallel }x-y{\mathrm{\parallel }}_2\mathrm{.}$$ We show that a strictly stronger version of this statement holds, answering one of the main open questions of [MMMR18]: “$\mathrm{\forall }y\in X$” in the above statement may be replaced with "$\forall y\in\mathbb R^d$\mathrm{"},sothat$f$notonlypreservesdistanceswithin$X$, but also distances to $X$ from the rest of space. Previously this stronger version was only known with the worse bound $m=O({\epsilon }^{-4}\log n)$. Our proof is via a tighter analysis of (a specific instantiation of) the embedding recipe of [MMMR18].