詹森-林登史特勞斯引理（Johnson-Lindenstrauss lemma）
/ JON-son LIN-den-strowss /
這裡有個聽起來好得不像真的事實：如果你有一團點活在一千維空間裡，你可以「隨機地」把它壓進區區幾十維，而幾乎所有點與點之間的距離都近乎不變地保留下來。這團點的形狀——誰靠近誰、東西相距多遠——即使你丟掉了大部分座標也得以保留。詹森-林登史特勞斯引理就是這個近乎奇蹟的精確、可證明的陳述，它支撐了一整箱降維工具。
引理說：對高維空間裡任意一組 n 個點與任意容差 epsilon，存在一個映射到約 (log n) / epsilon^2 階的目標維度 k 的線性映射，把每一對點之間的距離保留到 1 正負 epsilon 的因子之內。令人驚訝的是，目標維度 k 取決於點的「數量」n（且只是對數地）與精度 epsilon——卻「不」取決於原始維度，無論它多巨大。更驚人的是，這個映射可以是一個簡單的「隨機」投影：把每個點乘上一個隨機矩陣（高斯元素，甚至隨機正負 1 的元素）再重新縮放；該隨機映射有高機率奏效。證明是一個測度集中的論證——一個固定向量的隨機投影，其長度緊密集中在期望值附近，所以距離幾乎不動。
這條引理是隨機投影、速寫，以及大部分隨機化數值線性代數（包括隨機化 SVD）底下的理論基石：它保證你可以先壓縮資料、之後再計算，而失真受控。誠實的細則：1/epsilon^2 的依賴很陡——把容許的失真砍半，所需維度就變四倍——所以要高精度時 k 並不小。這個保證保留的是成對的「歐幾里得」距離（以及近似的內積），而非任意結構，而且它是一個機率性的最壞情況界：一個給定的隨機投影以高機率而非確定地奏效，而 log n 因子意味它在你有許多點卻只想保住距離時最有用，而非在你需要精確幾何時。
你有 n = 10,000 份文件，各以一個 100,000 維的詞頻向量表示，想依相似度分群。取 epsilon = 0.2，引理保證有一個隨機投影到約 (log 10000) / 0.04 = 約 230 維，把每一對距離保持在 20% 之內。在 230 維資料上分群於是快上數百倍，結果本質相同。
一個隨機投影壓縮維度，同時把所有成對距離保持在 1 正負 epsilon 之內。
目標維度取決於點的「數量」（對數地）與 1/epsilon^2，而非原始維度——但 1/epsilon^2 的代價很陡，而且這個保證是以高機率保留歐幾里得距離，並非確定地保留精確幾何。