Convergence properties of the randomized extended Gauss-Seidel and Kaczmarz methods
This work completes the theoretical foundation for two fundamental iterative linear system solvers, benefiting researchers and practitioners in numerical linear algebra and optimization.
The paper provides a unified theory of randomized Kaczmarz and Gauss-Seidel methods, proving that an extended randomized Gauss-Seidel converges linearly to the least norm solution for underdetermined systems, where the standard method fails. The theory covers all system types (over/underdetermined, consistent/inconsistent).
The Kaczmarz and Gauss-Seidel methods both solve a linear system $\bf{X}\bfβ = \bf{y}$ by iteratively refining the solution estimate. Recent interest in these methods has been sparked by a proof of Strohmer and Vershynin which shows the randomized Kaczmarz method converges linearly in expectation to the solution. Lewis and Leventhal then proved a similar result for the randomized Gauss-Seidel algorithm. However, the behavior of both methods depends heavily on whether the system is under or overdetermined, and whether it is consistent or not. Here we provide a unified theory of both methods, their variants for these different settings, and draw connections between both approaches. In doing so, we also provide a proof that an extended version of randomized Gauss-Seidel converges linearly to the least norm solution in the underdetermined case (where the usual randomized Gauss Seidel fails to converge). We detail analytically and empirically the convergence properties of both methods and their extended variants in all possible system settings. With this result, a complete and rigorous theory of both methods is furnished.