Abstract
We introduce and study the notion of an outer bi-Lipschitz extension of a mapbetween Euclidean spaces. The notion is a natural analogue of the notion of aLipschitz extension of a Lipschitz map. We show that for every map $f$ thereexists an outer bi-Lipschitz extension $f'$ whose distortion is greater thanthat of $f$ by at most a constant factor. This result can be seen as acounterpart of the classic Kirszbraun theorem for outer bi-Lipschitzextensions. We also study outer bi-Lipschitz extensions of near-isometric mapsand show upper and lower bounds for them. Then, we present applications of ourresults to prioritized and terminal dimension reduction problems. * We prove a prioritized variant of the Johnson-Lindenstrauss lemma: given aset of points $X\subset \mathbb{R}^d$ of size $N$ and a permutation ("priorityranking") of $X$, there exists an embedding $f$ of $X$ into $\mathbb{R}^{O(\logN)}$ with distortion $O(\log \log N)$ such that the point of rank $j$ has only$O(\log^{3 + \varepsilon} j)$ non-zero coordinates - more specifically, all butthe first $O(\log^{3+\varepsilon} j)$ coordinates are equal to $0$; thedistortion 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 anopen question by Elkin, Filtser, and Neiman about prioritized dimensionreductions. * We prove that given a set $X$ of $N$ points in $\mathbb{R}^d$, there existsa terminal dimension reduction embedding of $\mathbb{R}^d$ into$\mathbb{R}^{d'}$, where $d' = O\left(\frac{\log N}{\varepsilon^4}\right)$,which preserves distances $\|x-y\|$ between points $x\in X$ and $y \in\mathbb{R}^{d}$, up to a multiplicative factor of $1 \pm \varepsilon$. Thisimproves a recent result by Elkin, Filtser, and Neiman. The dimension reductions that we obtain are nonlinear, and this nonlinearityis necessary.