论文标题
用于计算近似空空间的快速随机算法
A Fast Randomized Algorithm for Computing an Approximate Null Space
论文作者
论文摘要
数值线性代数中的随机算法可以快速，可扩展和稳健。本文研究了素描对与高肤色矩阵最小的奇异值相对应的右奇异向量的效果。我们通过使用乘法扰动理论检查溶液的质量，使用随机化来分析Gilbert，Park和Wakin的快速算法，以发现尾随的右奇异向量。对于$ m \ times n $（$ m \ geq n $）矩阵，该算法以复杂性$ o（mn \ log n +n^3）$运行，该算法比标准$ o（mn^2）$方法快。在应用程序中，数值实验显示出很大的加速，包括AAA算法的$ 30 \ times $加速和$ 10 \ times $ speedup，$ speedup对于总和正方形问题。
Randomized algorithms in numerical linear algebra can be fast, scalable and robust. This paper examines the effect of sketching on the right singular vectors corresponding to the smallest singular values of a tall-skinny matrix. We analyze a fast algorithm by Gilbert, Park and Wakin for finding the trailing right singular vectors using randomization by examining the quality of the solution using multiplicative perturbation theory. For an $m\times n$ ($m\geq n$) matrix, the algorithm runs with complexity $O(mn\log n +n^3)$ which is faster than the standard $O(mn^2)$ methods. In applications, numerical experiments show great speedups including a $30\times$ speedup for the AAA algorithm and $10\times$ speedup for the total least squares problem.
