Nonlinear Dimension Reduction via Outer Bi-Lipschitz Extensions

We introduce and study the notion of an outer bi-Lipschitz extension of a map between Euclidean spaces. The notion is a natural analogue of the notion of a Lipschitz extension of a Lipschitz map. We show that for every map $f$ there exists an outer bi-Lipschitz extension $f^{\mathrm{\prime }}$ whose distortion is greater than that of $f$ by at most a constant factor. This result can be seen as a counterpart of the classic Kirszbraun theorem for outer bi-Lipschitz extensions. We also study outer bi-Lipschitz extensions of near-isometric maps and show upper and lower bounds for them. Then, we present applications of our results to prioritized and terminal dimension reduction problems.

• We prove a prioritized variant of the Johnson-Lindenstrauss lemma: given a set of points $X\subset {\mathbb{R}}^d$ of size $N$ and a permutation (“priority ranking”) of $X$, there exists an embedding $f$ of $X$ into $$\mathbb{R}$^{O(\log N)}$withdistortion$O(\log \log N)$suchthatthepointofrank$j$hasonly$O(\log^{3 + \varepsilon} j)$ non-zero coordinates - more specifically, all but the first $O({\log }^{3+\epsilon }j)$ coordinates are equal to $0$; the distortion of $f$ restricted to the first $j$ points (according to the ranking) is at most $O(\log \log j)$. The result makes a progress towards answering an open question by Elkin, Filtser, and Neiman about prioritized dimension reductions.
• We prove that given a set $X$ of $N$ points in ${\mathbb{R}}^d$, there exists a terminal dimension reduction embedding of ${\mathbb{R}}^d$ into ${\mathbb{R}}^{d^{\mathrm{\prime }}}$, where $d^{\mathrm{\prime }}=O\left(\frac{\log N}{{\epsilon }^4}\right)$, which preserves distances $\mathrm{\parallel }x-y\mathrm{\parallel }$ between points $x\in X$ and $y \in $\mathbb{R}$^{d}$,uptoamultiplicativefactorof$1 \pm \varepsilon$. This improves a recent result by Elkin, Filtser, and Neiman. The dimension reductions that we obtain are nonlinear, and this nonlinearity is necessary.