隨機化奇異值分解（randomized SVD）

一個巨大的資料矩陣——數百萬列與行——往往藏著簡單性：它幾乎所有有意義的內容都落在寥寥幾個主導方向上，其餘是雜訊。計算完整的奇異值分解來找出那些方向極其昂貴。隨機化 SVD 是一條意外強大的捷徑：它用一劑隨機性快速找出真正重要的那幾個方向、跳過其餘，並以一小部分的時間交出一個近乎最佳的低秩逼近。

其想法是先用隨機投影把大矩陣「速寫」成一個小矩陣。要逼近一個 m×n 矩陣 A 的前 k 個結構：抽一個隨機的 n×(k+p) 矩陣 Omega（多幾行 p 以策安全），構造速寫 Y = A * Omega——把 A 乘上隨機向量會混合它的行，並有高機率使 Y 的行張成與 A 前 k 個左奇異向量幾乎相同的空間。把 Y 正交化（一個薄的 QR 分解）得到一個 m×(k+p) 矩陣 Q，其行構成那個被捕捉子空間的標準正交基底。然後把 A 投影下來：B = Q^T * A 現在是一個小小的 (k+p)×n 矩陣，你對 B 跑一個普通、便宜的 SVD，再透過 Q 把結果抬回去。成本從完整 SVD 的 O(m*n*min(m,n)) 降到約 O(m*n*k) 加上小型稠密分解——當 k 遠小於 m 與 n 時是巨大的節省。

隨機化 SVD 是隨機化數值線性代數的旗艦，也是大規模 PCA、推薦系統與資料壓縮背後的實用引擎。誠實之處：結果是「近似」的，誤差由 A 的奇異值衰減多快掌控——當頻譜迅速下降（一個真正低秩加雜訊的矩陣）時它極佳，當尾部平坦時則較弱。過取樣參數 p 與一兩次「冪迭代」（把 A*Omega 換成 (A*A^T)^q * A * Omega 以銳化主導方向）控制精度。誤差是「隨機」的——它以高機率成立，而非確定——但失敗機率被壓到微乎其微，而 Eckart-Young 定理仍告訴你所瞄準的最佳可能秩 k 誤差。