A novel multi-step randomized Kaczmarz method for solving large linear systems
摘要
In this paper, we propose a novel multi-step randomized Kaczmarz method with cyclic column updates and greedy residual-driven row sampling for solving large linear systems. This method combines a row-wise local maximum residual strategy and cyclic column updates, and employs multiple iterative updates within each step, resulting in a non-stationary inner-outer iteration scheme. This architecture enables simultaneous utilization of both row-space and column-space geometric information while maintaining low computational overhead. Based on key inequalities and related theoretical results, we prove the convergence of the proposed multi-step randomized Kaczmarz method for matrices with full column rank and derive an upper bound on its expected convergence rate. Numerical experiments on both synthetic and real-world datasets demonstrate that the new multi-step randomized Kaczmarz method outperforms existing approaches in terms of efficiency.