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

来源：同济大学学报·自然科学版杂志2024年第8期北京时间：

作者：叶雨欣，殷俊锋

单位：同济大学 数学科学学院，上海 200092

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

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

基金资助：国家自然科学基金（11971354）