Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decomposition
Cameron Musco Massachusetts Institute of Technology, EECS Cambridge, MA 02139, USA、Christopher Musco Massachusetts Institute of Technology, EECS Cambridge, MA 02139, USA
Abstract
Since being analyzed by Rokhlin, Szlam, and Tygert [1] and popularized by Halko, Martinsson, and Tropp [2], randomized Simultaneous Power Iteration has become the method of choice for approximate singular value decomposition. It is more accurate than simpler sketching algorithms, yet still converges quickly for any matrix, independently of singular value gaps. After $\tilde{O}(1/\epsilon)$ iterations, it gives a low-rank approximation within $(1+\epsilon)$ of optimal for spectral norm error.
中文速览
近十年来，随机化「同步幂迭代」（Simultaneous Power Iteration）已成为求矩阵近似奇异值分解（SVD）的主流方法，它能在不依赖奇异值间距的前提下、经过约 O(1/ε) 轮迭代后给出高质量的低秩近似，但更快的理论下限一直悬而未决。本文提出了一种基于经典 Block Lanczos 思路的随机块 Krylov 方法（Block Krylov Iteration），将所需迭代次数压缩到 O(1/√ε)，给出了首个不依赖奇异值间距的 Krylov 子空间方法理论保证。与此同时，论文还指出仅靠谱范数低秩近似误差并不能保证恢复高质量主成分（PCA），并首次从理论上证明块 Krylov 方法与改进后的同步迭代算法均能为每个近似奇异向量提供几乎最优的逐向量 PCA 精度保证，在真实数据集上的实验也证实了新算法相较同步迭代的显著优势。这一工作不仅填补了经典 Krylov/Lanczos 方法缺乏严格间距无关分析的理论空白，也为数据分析和机器学习应用中对主成分质量有更高要求的场景提供了更可靠的算法基础。
原文 arXiv:1504.05477;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1504.05477v4