Johnson-Lindenstrauss 引理（Johnson-Lindenstrauss lemma）

Johnson-Lindenstrauss 引理是降維的理論執照：它說高維歐氏空間中任何有限點集，可由一個簡單的隨機線性映射映入維度僅與點數成對數關係的空間，同時把所有成對距離保持到一個小的相對誤差之內。這正是演算法能把資料從數千維壓縮到數十維、卻仍有可證明的保距保證的原因，也是範數集中最乾淨的應用。

陳述如下：對 R^d 中任意點集 x_1、…、x_N 與任意容差 eps in (0, 1)，存在線性映射 f: R^d -> R^k，目標維度 k = O(eps^(-2) log N)，使得對每一對，(1 - eps) ||x_i - x_j||^2 <= ||f(x_i) - f(x_j)||^2 <= (1 + eps) ||x_i - x_j||^2。目標維度 k 只依賴 N 與 eps——「不」依賴原維度 d。證明是純粹的集中。取 f(x) = (1/sqrt(k)) G x，其中 G 是 k×d 的獨立 N(0,1) 元素矩陣（或 Rademacher，或稀疏）。對任何固定向量 u，||f(u)||^2 / ||u||^2 是 k 個獨立標準高斯平方的平均，是均值為 1 的卡方/k 變數，由 Bernstein 它集中在 1 附近且 P(失真 > eps) <= 2 exp(-c k eps^2)。取 k ~ eps^(-2) log N 使此失敗機率小於 1/N^2，再對 binom(N, 2) 個成對差向量取聯集界，即以正機率同時保證所有距離被保持——故此映射存在（事實上隨機映射以高機率即可）。

JL 是隨機化數值線性代數、草圖法、局部敏感哈希與快速近似最近鄰的基礎；它使隨機投影成為有原則的前處理步驟而非啟發法。誠實的提醒既尖銳又重要。第一，log N 的依賴本質上是最佳的（Larsen-Nelson 下界），故一般無法勝過 O(eps^(-2) log N)。第二，JL 保持「固定有限點集」之間的「成對」距離，而非子空間中每個向量的範數——保持整個子空間需要更強的子空間嵌入／受限等距性質，k 須隨子空間維度縮放。第三，保證是針對平方距離至 (1 +/- eps)；它不會以同等保真度保持角度或內積，除非重述界，且它不保持非歐（如 L_1）距離——L_1 沒有 JL 引理。