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

约翰逊-林登斯特劳斯定理(Johnson–Lindenstrauss theorem)，又称约翰逊-林登斯特劳斯引理(Johnson–Lindenstrauss lemma)，是由William Johnson（英语：William_B._Johnson_(mathematician)）和Joram Lindenstrauss（英语：Joram_Lindenstrauss）于1984年提出的一个关于降维的著名定理，在现代机器学习，尤其是压缩感知、降维、形状分析（英语：Nonlinear_dimensionality_reduction#Manifold_learning_algorithms）和分布学习（英语：Density_estimation）等领域中有很重要的应用。

这个定理告诉我们，一个高维空间中的点集，可以被线性地镶嵌到低维空间中，同时其空间结构只遭受比较小的形变。约翰逊-林登斯特劳斯定理的证明，还说明了如何用随机投影法（英语：Random_projection）明确地求出这个变换，所用的算法只需要随机多项式时间。当然，降维不是免费的：如果要求形变很少的话，代价（英语：trade-off）是被嵌入的低维空间维数不能很低；反之亦然，如果要求将点集嵌入很低维的空间，那么就不能很好地控制结构形变的程度。

因为能将维数下降到样本量的对数阶，更兼所用的变换是线性的、显式的还可以被快速计算，约翰逊-林登斯特劳斯定理是一个力度非常强的结论。

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

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

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

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

这么多的维数。

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