# Nonlinear Dimension Reduction via Outer Bi-Lipschitz Extensions

arXiv: https://arxiv.org/abs/1811.03591 · HTML: https://mlsanity.com/paper/1811.03591/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Nov 2018.

## Built on by (most cited first, 7 of 7)

- [Towards Optimal Lower Bounds for k-median and k-means Coresets](https://mlsanity.com/paper/2202.12793/) (2022)
- [An Empirical Evaluation of k-Means Coresets](https://mlsanity.com/paper/2207.00966/) (2022)
- [Terminal Embeddings in Sublinear Time](https://mlsanity.com/paper/2110.08691/) (2021)
- [A Normalized Bottleneck Distance on Persistence Diagrams and Homology Preservation under Dimension Reduction](https://mlsanity.com/paper/2306.06727/) (2023)
- [On Outer Bi-Lipschitz Extensions of Linear Johnson-Lindenstrauss Embeddings of Low-Dimensional Submanifolds of ℝN](https://mlsanity.com/paper/2206.03376/) (2022)
- [Distance-Preserving Representations for Genomic Spatial Reconstruction](https://mlsanity.com/paper/2408.00911/) (2024)
- [Beyond Worst-Case Dimensionality Reduction for Sparse Vectors](https://mlsanity.com/paper/2502.19865/) (2025)

## Abstract (arXiv)

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 Xsubset ℝd of size N and a permutation ("priority ranking") of X, there exists an embedding f of X into ℝO(log N) with distortion O(log log N) such that the point of rank j has only O(log3 + varepsilon j) non-zero coordinates - more specifically, all but the first O(log3+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(loglog 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 ℝd, there exists a terminal dimension reduction embedding of ℝd into ℝd', where d' = Oleft(fraclog Nvarepsilon4right), which preserves distances |x-y| between points x∈ X and y ∈ ℝd, up to a multiplicative factor of 1 ± varepsilon. This improves a recent result by Elkin, Filtser, and Neiman. The dimension reductions that we obtain are nonlinear, and this nonlinearity is necessary.