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