论文标题
用于计算低率矩阵近似的传递随机LU算法
Pass-Efficient Randomized LU Algorithms for Computing Low-Rank Matrix Approximation
论文作者
论文摘要
低级别矩阵近似在分析科学计算，工程应用和数据科学中产生的数据时非常有用。但是，随着数据大小的增长，传统的低级矩阵近似方法（例如SVD和CPQR）要么昂贵，要么无法提供足够准确的结果。一种解决方案是使用随机的低级矩阵近似方法，例如随机SVD，以及在极大的数据集上随机LU分解。在本文中，我们关注随机LU分解方法。首先，我们采用重新配合程序来执行现有的随机LU算法的功率迭代，以补偿由功率方法引起的舍入错误。然后，我们提出了一种新型的随机LU算法，称为Powerlu，以解决固定的低级别近似问题。 Powerlu允许输入矩阵的任意数量，$ v \ geq 2 $。回想一下，现有的随机LU分解仅允许均匀数量的传球。我们证明了Powerlu与现有的随机LU之间的理论关系。数值实验表明，我们提出的Powerlu通常比现有的随机LU分解快，同时保持准确。对于固定的精度低率矩阵近似问题，我们还提出了一个称为powerlu_fp的Powerlu版本。 Powerlu_FP基于本文提出的有效阻止的自适应等级确定算法4.1。我们提出的数值实验表明，Powerlu_FP可以达到几乎相同的精度，并且比Martinsson和Voronin的随机阻塞QB算法更快。我们最终基于LU分解提出了一种单通算法。测试表明，我们的单通行算法的准确性与现有的单通行算法相当。
Low-rank matrix approximation is extremely useful in the analysis of data that arises in scientific computing, engineering applications, and data science. However, as data sizes grow, traditional low-rank matrix approximation methods, such as SVD and CPQR, are either prohibitively expensive or cannot provide sufficiently accurate results. A solution is to use randomized low-rank matrix approximation methods such as randomized SVD , and randomized LU decomposition on extremely large data sets. In this paper, we focus on the randomized LU decomposition method. First, we employ a reorthogonalization procedure to perform the power iteration of the existing randomized LU algorithm to compensate for the rounding errors caused by the power method. Then we propose a novel randomized LU algorithm, called PowerLU, for the fixed low-rank approximation problem. PowerLU allows for an arbitrary number of passes of the input matrix, $v \geq 2$. Recall that the existing randomized LU decomposition only allows an even number of passes. We prove the theoretical relationship between PowerLU and the existing randomized LU. Numerical experiments show that our proposed PowerLU is generally faster than the existing randomized LU decomposition, while remaining accurate. We also propose a version of PowerLU, called PowerLU_FP, for the fixed precision low-rank matrix approximation problem. PowerLU_FP is based on an efficient blocked adaptive rank determination Algorithm 4.1 proposed in this paper. We present numerical experiments that show that PowerLU_FP can achieve almost the same accuracy and is faster than the randomized blocked QB algorithm by Martinsson and Voronin. We finally propose a single-pass algorithm based on LU factorization. Tests show that the accuracy of our single-pass algorithm is comparable with the existing single-pass algorithms.
