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

约翰逊-林登斯特劳斯定理(Johnson–Lindenstrauss theorem)，又称约翰逊-林登斯特劳斯引理(Johnson–Lindenstrauss lemma)，是由和于1984年提出的一个关于降维的著名定理，在现代机器学习，尤其是压缩感知、降维、和等领域中有很重要的应用。 这个定理告诉我们，一个高维空间中的点集，可以被线性地镶嵌到低维空间中，同时其空间结构只遭受比较小的形变。约翰逊-林登斯特劳斯定理的证明，还说明了如何用明确地求出这个变换，所用的算法只需要随机多项式时间。当然，降维不是免费的：如果要求形变很少的话，是被嵌入的低维空间维数不能很低；反之亦然，如果要求将点集嵌入很低维的空间，那么就不能很好地控制结构形变的程度。 因为能将维数下降到样本量的对数阶，更兼所用的变换是线性的、显式的还可以被快速计算，约翰逊-林登斯特劳斯定理是一个力度非常强的结论。