Convergence Properties of the Randomized Extended Gauss--Seidel and Kaczmarz Methods

Abstract

The Kaczmarz and Gauss--Seidel methods both solve a linear system $\boldsymbol{X}{\boldsymbol{\beta}} = \boldsymbol{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 underdetermined 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.