论文标题
在外部Bi-lipschitz上，线性的Johnson-Lindenstrauss嵌入$ \ Mathbb {r}^n $的低维submanifolds的嵌入
On Outer Bi-Lipschitz Extensions of Linear Johnson-Lindenstrauss Embeddings of Low-Dimensional Submanifolds of $\mathbb{R}^N$
论文作者
论文摘要
令$ \ mathcal {m} $为$ \ mathbb {r}^n $的紧凑型$ d $ - d $ d $ d $ d $ d $ d $ d $ d $ d $ d $ d $ d $ d $ d $ d $ d $ d $ d $ d $ d $ d $ d $ d $ d $ d $ d $ d $ d $ d $ d $ d $ d $ d $ d $ d $ d $ d $ d $ d $ d $ d $ \ d $ \ d $ \ mathbb {r}^n $，符合$τ$和音量$ v _ {\ mathcal m} $。修复（0,1）$中的$ε\。在本文中，我们证明了非线性函数$ f：\ mathbb {r}^n \ rightArrow \ mathbb {r}^{m} $ cy以$ m \ leq c \ left（d /ε^2 \ right）\ log \ log \ weft（\ frac {\ frac {\ sqrt { \ right）$，以至于$$（1-ε）\ | {\ bf x} - {\ bf y} \ | _2 \ leq \ left \ | f（{\ bf x}） - f（{\ bf y}）\ right \ | _2 \ leq（1 +ε）\ | {\ bf x} - {\ bf y} \ | _2 $$保留所有$ {\ bf x} \ in \ mathcal {m} $和$ {\ bf y} \ in \ mathbb {r}^n $。实际上，$ f $不仅从$ \ mathcal {m} $中充当bi-lipschitz函数，在$ \ mathbb {r}^{m}^{m}^{m}^$中，带有bi-lipschitz常数接近一个，而且大约保留了从$ \ nathcal {m} $中的所有距离，也可以保留所有距离的所有距离。此外，证明具有建设性，并产生了一种在实践中效果很好的算法。特别是，本文在经验上表明，这种非线性函数允许比标准线性的Johnson-Lindenstrauss 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.
