论文标题
快速，稳定的随机低级矩阵近似
Fast and stable randomized low-rank matrix approximation
论文作者
论文摘要
随机SVD已成为有效计算矩阵低级别近似值的极其成功的方法。特别是，Halko，Martinsson和Tropp的论文（Sirev 2011）包含广泛的分析，并且使其成为一种非常流行的方法。 $ m \ times n $矩阵的等级$ r $ a $近似值的典型复杂性为$ O（mn \ log n+（m+n）r^2）$ to tonge矩阵。经典的nystr {Ö} m方法要快得多，但仅适用于阳性半限制矩阵。 This work studies a generalization of Nystr{ö}m method applicable to general matrices, and shows that (i) it has near-optimal approximation quality comparable to competing methods, (ii) the computational cost is the near-optimal $O(mn\log n+r^3)$ for dense matrices, with small hidden constants, and (iii) crucially, it can be implemented in a numerically stable fashion despite存在不良的伪verseverse。数值实验表明，通用的nyStr {Ö} m可以显着超过最先进的方法，尤其是当$ r \ gg 1 $时，达到10倍的速度。该方法也非常适合更新和降低矩阵。
Randomized SVD has become an extremely successful approach for efficiently computing a low-rank approximation of matrices. In particular the paper by Halko, Martinsson, and Tropp (SIREV 2011) contains extensive analysis, and has made it a very popular method. The typical complexity for a rank-$r$ approximation of $m\times n$ matrices is $O(mn\log n+(m+n)r^2)$ for dense matrices. The classical Nystr{ö}m method is much faster, but applicable only to positive semidefinite matrices. This work studies a generalization of Nystr{ö}m method applicable to general matrices, and shows that (i) it has near-optimal approximation quality comparable to competing methods, (ii) the computational cost is the near-optimal $O(mn\log n+r^3)$ for dense matrices, with small hidden constants, and (iii) crucially, it can be implemented in a numerically stable fashion despite the presence of an ill-conditioned pseudoinverse. Numerical experiments illustrate that generalized Nystr{ö}m can significantly outperform state-of-the-art methods, especially when $r\gg 1$, achieving up to a 10-fold speedup. The method is also well suited to updating and downdating the matrix.
