Cholesky分解的单Pass随机算法在秩亏最小二乘中的应用

The Application of Single-Pass Randomized Algorithm for Cholesky Decomposition in Rank Deficit Least Squares

摘要: 通常针对大规模的对称半正定矩阵求解最小二乘问题时，往往得不到精确解，而传统的矩阵分解方法在规模增大的情况下大大地增加了求解时间和复杂度，Cholesky分解的单pass随机算法只需对输入矩阵访问一次，因此本文将Cholesky分解的单pass随机算法与两种常见的求解最小二乘问题的方法结合，提出了两种新的求解最小二乘问题的算法，并将两者进行了比较，最后通过数值实验证明了这两种算法的有效性及可行性。

Abstract: Usually for large-scale symmetric semi-positive definite matrices to solve the least squares problem, often do not get the exact solution, and the traditional matrix factorization method greatly increases the solution time and complexity in the case of increasing scale, the Cholesky decomposition of the single-pass randomized algorithm only needs to access the input matrix once, so this paper combines the single-pass random algorithm of Cholesky decomposition with two common methods to solve the least squares problem, proposes two new algorithms for solving the least squares problem, compares the two, and finally proves the effectiveness and feasibility of the two algorithms through numerical experiments.