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

約翰遜-林登斯特勞斯定理(Johnson–Lindenstrauss theorem)，又稱約翰遜-林登斯特勞斯引理(Johnson–Lindenstrauss lemma)，是由William Johnson和Joram Lindenstrauss於1984年提出的一個關於降維的著名定理，在現代機器學習，尤其是壓縮感知、降維、形狀分析和分布學習等領域中有很重要的應用。

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

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

定理陳述

對任何給定的$\epsilon \in (0,1)$以及$N$維歐幾里德空間中的$m$個點$\{x_{1},\ldots ,x_{m}\}$，對於任意滿足條件$n>(\epsilon ^{2}/2-\epsilon ^{3}/3)^{-1}\log m$的正整數$n$，存在一個線性映射$f:\mathbb {R} ^{N}\to \mathbb {R} ^{n}$，將這$m$個點，從$\mathbb {R} ^{N}$(維數可能很高的空間)中映射到$\mathbb {R} ^{n}$(低維空間)中，同時「基本上」保持了點集成員兩兩之間的距離，即：對於任意兩個點$(x_{i},x_{j}):1\leq i<j\leq m$，都有

$(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}$

更進一步地，這個線性映射$f$還可以在隨機多項式時間內求出。

直觀理解

約翰遜-林登斯特勞斯定理揭示了一些關於降維映射深刻事實，其中一些還是違反簡單直覺的。因此，要想直觀地理解這個定理，對初學者來說，可能比從數學式子上讀懂證明還要難(反而此定理的證明只用到了比較簡單的關於投影的隨機誤差不等式)。舉例來說，定理的結論表明，度量形變程度的誤差參數$\epsilon$以及低維空間的維數$n$這兩個度量降維水準的關鍵量，均與原始數據所在的空間維數$N$或者原始的$m$個點具體為何種空間結構無關，這是很不平凡的。

最優性

約翰遜-林登斯特勞斯定理是不能被本質性地改進的，即：給定任意正整數$m$和誤差參數$\epsilon$，存在某個$N$以及$\mathbb {R} ^{N}$中的$m$個點，這個點集「難以降維」——也就是說，對任何一個滿足「基本保持點距」要求(即：$(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}$要對任意$(i,j):1\leq i<j\leq n$成立)的線性映射$f:\mathbb {R} ^{N}\to \mathbb {R} ^{n}$，它用來鑲嵌高維數據的那個低維空間(即$\mathbb {R} ^{n}$)，至少必須具有

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

這麼多的維數。

證明提要

定理可以用高年級大學生容易理解的方法證明，其思路是證明如下事實：多次獨立地重複進行隨機投影的試驗，每次試驗中隨機抽取的投影$f_{0}:\mathbb {R} ^{N}\to \mathbb {R} ^{n}$都有至少$1/n$的概率符合定理中對映射$f$全部的要求(顯然，驗證任何一個$f_{0}$是否符合這些要求只需$O(n^{2})$時間)，因此只要重複該獨立實驗$\omega (n)$次就能以逼近100%的概率產生至少一個符合要求的映射$f$。