约翰逊-林登斯特劳斯定理

对任何给定的${\displaystyle \epsilon \in (0,1)}$ 以及${\displaystyle N}$ 维欧几里德空间中的${\displaystyle m}$ 个点${\displaystyle \{x_{1},\ldots ,x_{m}\}}$ ，对于任意满足条件${\displaystyle n>(\epsilon ^{2}/2-\epsilon ^{3}/3)^{-1}\log m}$ 的正整数${\displaystyle n}$ ，存在一个线性映射${\displaystyle f:\mathbb {R} ^{N}\to \mathbb {R} ^{n}}$ ，将这${\displaystyle m}$ 个点，从${\displaystyle \mathbb {R} ^{N}}$ (维数可能很高的空间)中映射到${\displaystyle \mathbb {R} ^{n}}$ (低维空间)中，同时“基本上”保持了点集成员两两之间的距离，即：对于任意两个点${\displaystyle (x_{i},x_{j}):1\leq i<j\leq m}$ ，都有

${\displaystyle (1-\epsilon )\|x_{i}-x_{j}\|_{2}^{2}\leq \|f(x_{i})-f(x_{j})\|_{2}^{2}\leq (1+\epsilon )\|x_{i}-x_{j}\|_{2}^{2}}$ 

更进一步地，这个线性映射${\displaystyle f}$ 还可以在随机多项式时间内求出^[7]。

直观理解

约翰逊-林登斯特劳斯定理揭示了一些关于降维映射深刻事实，其中一些还是违反简单直觉的^[8]。因此，要想直观地理解这个定理，对初学者来说，可能比从数学式子上读懂证明还要难(反而此定理的证明只用到了比较简单的关于投影的随机误差不等式（英语：Concentration of measure）^[9])。举例来说，定理的结论表明，度量形变程度的误差参数${\displaystyle \epsilon }$ 以及低维空间的维数${\displaystyle n}$ 这两个度量降维水准的关键量，均与原始数据所在的空间维数${\displaystyle N}$ 或者原始的${\displaystyle m}$ 个点具体为何种空间结构无关，这是很不平凡的^[9]。

最优性

约翰逊-林登斯特劳斯定理是不能被本质性地改进的^[10]，即：给定任意正整数${\displaystyle m}$ 和误差参数${\displaystyle \epsilon }$ ，存在某个${\displaystyle N}$ 以及${\displaystyle \mathbb {R} ^{N}}$ 中的${\displaystyle m}$ 个点，这个点集“难以降维”——也就是说，对任何一个满足“基本保持点距”要求(即：${\displaystyle (1-\epsilon )\|x_{i}-x_{j}\|_{2}^{2}\leq \|f(x_{i})-f(x_{j})\|_{2}^{2}\leq (1+\epsilon )\|x_{i}-x_{j}\|_{2}^{2}}$ 要对任意${\displaystyle (i,j):1\leq i<j\leq n}$ 成立)的线性映射${\displaystyle f:\mathbb {R} ^{N}\to \mathbb {R} ^{n}}$ ，它用来镶嵌高维数据的那个低维空间(即${\displaystyle \mathbb {R} ^{n}}$ )，至少必须具有

${\displaystyle n=\Omega \left({\frac {\log m}{\epsilon ^{2}}}\right)}$ 

这么多的维数^[11]。

证明提要

定理可以用高年级本科生容易理解的方法证明^[7][12]，其思路是证明如下事实：多次独立地重复进行随机投影的试验，每次试验中随机抽取的投影${\displaystyle f_{0}:\mathbb {R} ^{N}\to \mathbb {R} ^{n}}$ 都有至少${\displaystyle 1/n}$ 的概率符合定理中对映射${\displaystyle f}$ 全部的要求(显然，验证任何一个${\displaystyle f_{0}}$ 是否符合这些要求只需${\displaystyle O(n^{2})}$ 时间)，因此只要重复该独立实验${\displaystyle \omega (n)}$ 次就能以逼近100%的概率产生至少一个符合要求的映射${\displaystyle f}$ 。