An Accelerated Randomized Kaczmarz Algorithm
Ji Liu Department of Computer Sciences, University of Wisconsin-Madison, Madison, WI 53706-1685 Department of Computer Sciences, 1210 W. Dayton St., Madison, WI 53706-1685 and Stephen J. Wright Department of Computer Sciences, University of Wisconsin-Madison, Madison, WI 53706-1685
Abstract
The randomized Kaczmarz (RK) algorithm is a simple but powerful approach for solving consistent linear systems $Ax=b$ . This paper proposes an accelerated randomized Kaczmarz (ARK) algorithm with better convergence than the standard RK algorithm on ill conditioned problems. The per-iteration cost of RK and ARK are similar if $A$ is dense, but RK is much more able to exploit sparsity in $A$ than is ARK. To deal with the sparse case, an efficient implementation for ARK, called SARK, is proposed. A comparison of convergence rates and average per-iteration complexities among RK, ARK, and SARK is given, taking into account different levels of sparseness and conditioning. Comparisons with the leading deterministic algorithm — conjugate gradient applied to the normal equations — are also given. Finally, the analysis is validated via computational testing.
中文速览
大规模线性方程组 Ax=b 的高效求解是科学计算的核心问题，随机卡兹马尔兹算法（Randomized Kaczmarz，RK）因每步只处理一行数据而备受关注，但在病态（ill-conditioned）问题上收敛慢。本文将 Nesterov 加速思想引入 RK，提出加速随机卡兹马尔兹算法（Accelerated Randomized Kaczmarz，ARK），理论上证明其在矩阵条件数较差时收敛速度显著优于标准 RK；针对 ARK 在稀疏矩阵上因中间向量稠密而丧失稀疏优势的问题，进一步设计了缓存更新策略 SARK，将每步平均计算量从 O(n) 降至 O(√δ·n)（δ 为矩阵非零元素比例）。文章给出了 RK、ARK、SARK 在不同稀疏度和条件数组合下的理论性能对比，并与共轭梯度法进行了比较，最终通过数值实验验证了理论分析，为实际应用中算法选择提供了量化指导。
原文 arXiv:1310.2887;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1310.2887v2