基于Count Sketch的预处理贪婪Kaczmarz方法

Preconditioning Greedy Kaczmarz Method Based on Count Sketch

摘要:

在贪婪Kaczmarz方法中， 通过对系数矩阵进行正交三角分解引入右预处理子能够提高贪婪Kaczmarz方法的收敛速率。但在系数矩阵的行数远大于列数的情况下， 正交三角分解的成本过高。为降低预处理的成本， 通过引入Count Sketch变换， 提出了基于Count Sketch的预处理贪婪Kaczmarz方法， 并对新方法进行了收敛性分析。理论分析说明了新方法在系数矩阵条件数较大时比已有方法具有更好的收敛速率。数值实验验证了新方法的有效性。

Abstract:

The convergence rate of greedy Kaczmarz method can be improved by introducing right preconditioner through orthogonal triangularization of coefficient matrix. However， when the number of rows of the coefficient matrix is much larger than the number of columns， the cost of orthogonal triangularization is too high. By introducing Count Sketch transform， a preconditioning greedy Kaczmarz method based on Count Sketch is proposed to reduce the cost. Convergence analysis of the new algorithm is provided， and the theoretical analysis shows that the new method has better convergence rate than the existing method when the condition number of coefficient matrix is large. The numerical experiments verified the effectiveness.