随机化 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、推荐系统以及现代数据科学流水线背后的标准引擎。