关于Kaczmarz的一类加速免伪逆贪婪块方法  

Accelerated Pseudo-Inverse-Free Greedy Block Methods in the Kaczmarz Algorithm Category

作　　者：颜鑫鹏 时文雅 郇战[1] 

机构地区：[1]常州大学阿里云大数据学院,江苏 常州

出　　处：《应用数学进展》2024年第1期466-484,共19页Advances in Applied Mathematics

摘　　要：块贪婪Kaczmarz方法在解决大规模一致线性系统方面取得了成功应用。然而在每次迭代步骤中,GBK方法都涉及伪逆计算,这不仅复杂化了计算并减慢了收敛速度,且不适合分布式实现。在本文中基于Sketching技术提出了两种免伪逆计算的GBK方法,分别是杠杆得分抽样免伪逆GBK方法和稀疏随机投影免伪逆GBK方法,其算法效率更加高效,收敛速度可以达到指数收敛。为了进一步加快收敛速度,我们还提出了CountSketch免伪逆重力球GBK方法、杠杆得分抽样免伪逆重力球GBK方法和稀疏随机投影免伪逆重力球GBK方法。为了验证新方法的有效性,我们进行了一些数值示例。结果表明,这些新方法在解决大规模一致线性系统方面具有很高的效率和准确性。The Greedy Block Kaczmarz (GBK) method has been successfully applied in solving large-scale con-sistent linear systems. However, each iteration of the GBK method involves the computation of pseudoinverses, which complicates the process, slows down convergence, and is ill-suited for dis-tributed implementations. In this paper, we introduce two free pseudoinverse GBK methods based on Sketching techniques: the Leverage Score Sampling Free Pseudoinverse GBK method and the Sparse Random Projection Free Pseudoinverse GBK method. These algorithms exhibit higher effi-ciency and can achieve exponential rates of convergence. To further accelerate convergence, we also propose the Count Sketch Free Pseudoinverse Heavy Ball GBK method, the Leverage Score Sampling Free Pseudoinverse Heavy Ball GBK method, and the Sparse Random Projection Free Pseudoinverse Heavy Ball GBK method. The effectiveness of these new methods is demonstrated through several numerical examples, showing that they are highly efficient and accurate in addressing large-scale consistent linear systems.

关 键 词：贪婪块Kaczmarz方法 收敛性 大规模相容线性方程组 矩阵Sketching技术 免伪逆计算 

分 类 号：TP3[自动化与计算机技术—计算机科学与技术]