On Outer Bi-Lipschitz Extensions of Linear Johnson-Lindenstrauss Embeddings of Low-Dimensional Submanifolds of \mathbb{R}^N

arXiv2206.03376MaRDI QIDQ6401375FDOQ6401375

Authors: M. A. Iwen, Mark Philip Roach 

Publication date: 7 June 2022

Abstract: Let $mathcalM$ be a compact $d$-dimensional submanifold of $mathbb{R}^N$ with reach $au$ and volume $V_{mathcalM}$. Fix $epsilonin(0,1)$. In this paper we prove that a nonlinear function $f:mathbb{R}^{N}ightarrowmathbb{R}^m$ exists with $mleqCleft(d/epsilo{n}^{2}ight)logleft(fracsqrt[d]V_{mathcalM}auight)$ such that ${\displaystyle }$(1 - epsilon) | {�f x} - {�f y} |_2 leq left| f({�f x}) - f({�f y}) ight|_2 leq (1 + epsilon) | {�f x} - {�f y} |_2${\displaystyle }$ holds for all $$ and $$. In effect, $f$ not only serves as a bi-Lipschitz function from $mathcalM$ into $mathbb{R}^m$ with bi-Lipschitz constants close to one, but also approximately preserves all distances from points not in $mathcalM$ to all points in $mathcalM$ 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.

Has companion code repository: https://github.com/markphiliproach/terminalembedding

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Lipschitz and coarse geometry of metric spaces (51F30) Metric embeddings as related to computational problems and algorithms (68R12)

This page was built for publication: On Outer Bi-Lipschitz Extensions of Linear Johnson-Lindenstrauss Embeddings of Low-Dimensional Submanifolds of $\mathbb{R}^N$

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6401375)