約翰遜-林登斯特勞斯定理

約翰遜-林登斯特勞斯定理(Johnson–Lindenstrauss theorem)，又稱約翰遜-林登斯特勞斯引理(Johnson–Lindenstrauss lemma)，是由William Johnson（英語：William_B._Johnson_(mathematician)）和Joram Lindenstrauss（英語：Joram_Lindenstrauss）於1984年提出的一個關於降維的著名定理^[1]，在現代機器學習，尤其是壓縮感知、降維、形狀分析（英語：Nonlinear_dimensionality_reduction#Manifold_learning_algorithms）和分布學習（英語：Density_estimation）等領域中有很重要的應用^[2][3][4][5]。

這個定理告訴我們，一個高維空間中的點集，可以被線性地鑲嵌到低維空間中，同時其空間結構只遭受比較小的形變^[6]。約翰遜-林登斯特勞斯定理的證明，還說明了如何用隨機投影法（英語：Random_projection）明確地求出這個變換，所用的算法只需要隨機多項式時間^[7]。當然，降維不是免費的：如果要求形變很少的話，代價（英語：trade-off）是被嵌入的低維空間維數不能很低；反之亦然，如果要求將點集嵌入很低維的空間，那麼就不能很好地控制結構形變的程度。

因為能將維數下降到樣本量的對數階，更兼所用的變換是線性的、顯式的還可以被快速計算，約翰遜-林登斯特勞斯定理是一個力度非常強的結論。

定理陳述

對任何給定的${\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}$。