# On Outer Bi-Lipschitz Extensions of Linear Johnson-Lindenstrauss Embeddings of Low-Dimensional Submanifolds of ℝN

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 24 references that are in the map.
- First posted on arXiv 7 Jun 2022.

## Builds on (most cited first, 6 of 6)

- [Optimality of the Johnson-Lindenstrauss Lemma](https://mlsanity.com/paper/1609.02094/) (2016)
- [Optimal terminal dimensionality reduction in Euclidean space](https://mlsanity.com/paper/1810.09250/) (2018)
- [Lower Memory Oblivious (Tensor) Subspace Embeddings with Fewer Random Bits: Modewise Methods for Least Squares](https://mlsanity.com/paper/1912.08294/) (2019)
- [Nonlinear Dimension Reduction via Outer Bi-Lipschitz Extensions](https://mlsanity.com/paper/1811.03591/) (2018)
- [Terminal Embeddings in Sublinear Time](https://mlsanity.com/paper/2110.08691/) (2021)
- [On Fast Johnson-Lindenstrauss Embeddings of Compact Submanifolds of ℝN with Boundary](https://mlsanity.com/paper/2110.04193/) (2021)

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

- [Dimension-Independent Kernel ε-Covers](https://mlsanity.com/paper/2306.16516/) (2023)

## Abstract (arXiv)

Let M be a compact d-dimensional submanifold of ℝN with reach τ and volume Vmathcal M. Fix ε ∈ (0,1). In this paper we prove that a nonlinear function f: ℝN rightarrow ℝm exists with m ≤ C left(d / ε2 right) log left(frac√[d]Vmathcal Mτ right) such that (1 - ε) | bf x - bf y |2 ≤ left| f(bf x) - f(bf y) right|2 ≤ (1 + ε) | bf x - bf y |2 holds for all bf x ∈ M and bf y ∈ ℝN. In effect, f not only serves as a bi-Lipschitz function from M into ℝm with bi-Lipschitz constants close to one, but also approximately preserves all distances from points not in M to all points in M in its image. Furthermore, the proof is constructive and yields an algorithm which works well in practice. In particular, it is empirically demonstrated herein that such nonlinear functions allow for more accurate compressive nearest neighbor classification than standard linear Johnson-Lindenstrauss embeddings do in practice.