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

Preconditioning Greedy Kaczmarz Method Based on Count Sketch

作　　者：叶雨欣 殷俊锋[1] YE Yuxin;YIN Junfeng(School of Mathematical Sciences,Tongji University,Shanghai 200092,China)

机构地区：[1]同济大学数学科学学院,上海200092

出　　处：《同济大学学报（自然科学版）》2024年第8期1305-1311,共7页Journal of Tongji University:Natural Science

基　　金：国家自然科学基金(11971354)。

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

关 键 词：Kaczmarz方法 预处理 Count Sketch 收敛性 

分 类 号：O241.6[理学—计算数学]