隨機化 SVD

當矩陣龐大無比——數百萬行列時，計算完整 SVD 毫無指望，而你通常本來也只想要前 k 個奇異三元組。隨機化 SVD 是一條優美而簡單的捷徑：與其探測每個方向，不如向矩陣拋去一小撮隨機向量，讓它們揭示作用之所在。它們大概率會主要落在主導子空間內。

配方分兩步。第一步（找出值域）：抽取一個 n×(k+p) 的隨機高斯矩陣 Omega（p 是小的過採樣餘量，比如 5 到 10），構造 Y = A Omega，再用 QR 把 Y 標準正交化，得到一個 m×(k+p) 矩陣 Q，其列近似張成 A 的主導左奇異子空間。第二步（解小問題）：構造小矩陣 B = Q^T A，取它的精確 SVD B = U_tilde Sigma V^T，並令 U = Q U_tilde。結果 U Sigma V^T 逼近 A 的截斷 SVD。

勝在成本。繁重的 SVD 只在極小的 (k+p)×n 矩陣 B 上做，從不在完整的 A 上做；A 本身只通過幾次矩陣乘法被觸及，而矩陣乘法又快又能極好地並行。對奇異譜快速衰減的矩陣，這能以經典 SVD 時間的一小部分交付前 k 個因子。

精度有可證明的保障。期望誤差接近最優的埃卡特-楊界 sigma_{k+1}，而過採樣加上可選的冪迭代（把 Y = A Omega 換成 Y = (A A^T)^q A Omega 以銳化譜間隙）會把它進一步收緊。隨機化 SVD 是大規模 PCA、推薦系統以及現代數據科學流水線背後的標準引擎。