On Outer Bi-Lipschitz Extensions of Linear Johnson-Lindenstrauss Embeddings of Low-Dimensional Submanifolds of $\mathbb{R}^N$
This provides a theoretical and practical advancement for dimensionality reduction in machine learning, particularly for tasks involving manifold-structured data, though it builds incrementally on existing embedding techniques.
The paper tackles the problem of extending linear Johnson-Lindenstrauss embeddings to preserve distances between points on a low-dimensional submanifold and all points in the ambient space, proving the existence of a nonlinear function with a dimension bound of m ≤ C(d/ε²) log(√[d]{V_M}/τ) that achieves (1±ε) distortion. It shows empirically that this method improves compressive nearest neighbor classification accuracy compared to standard linear embeddings.
Let $\mathcal{M}$ be a compact $d$-dimensional submanifold of $\mathbb{R}^N$ with reach $τ$ and volume $V_{\mathcal M}$. Fix $ε\in (0,1)$. In this paper we prove that a nonlinear function $f: \mathbb{R}^N \rightarrow \mathbb{R}^{m}$ exists with $m \leq C \left(d / ε^2 \right) \log \left(\frac{\sqrt[d]{V_{\mathcal M}}}τ \right)$ such that $$(1 - ε) \| {\bf x} - {\bf y} \|_2 \leq \left\| f({\bf x}) - f({\bf y}) \right\|_2 \leq (1 + ε) \| {\bf x} - {\bf y} \|_2$$ holds for all ${\bf x} \in \mathcal{M}$ and ${\bf y} \in \mathbb{R}^N$. In effect, $f$ not only serves as a bi-Lipschitz function from $\mathcal{M}$ into $\mathbb{R}^{m}$ with bi-Lipschitz constants close to one, but also approximately preserves all distances from points not in $\mathcal{M}$ to all points in $\mathcal{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.