Nonlinear Dimension Reduction via Outer Bi-Lipschitz Extensions
share
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⊂R^d of size N and a permutation ("priority ranking") of X, there exists an embedding f of X into R^O( N) with distortion O( N) such that the point of rank j has only O(^3 + ε j) non-zero coordinates - more specifically, all but the first O(^3+ε j) coordinates are equal to 0; the distortion of f restricted to the first j points (according to the ranking) is at most O( 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 R^d, there exists a terminal dimension reduction embedding of R^d into R^d', where d' = O( N/ε^4), which preserves distances x-y between points x∈ X and y ∈R^d, up to a multiplicative factor of 1 ±ε. This improves a recent result by Elkin, Filtser, and Neiman. The dimension reductions that we obtain are nonlinear, and this nonlinearity is necessary.
READ FULL TEXT