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'$ 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)}$ 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 but
the first $O(\log^{3+\varepsilon} 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'}$, 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$. This
improves a recent result by Elkin, Filtser, and Neiman.
  The dimension reductions that we obtain are nonlinear, and this nonlinearity
is necessary.
