Convergence properties of the randomized extended Gauss-Seidel and Kaczmarz methods

Understand

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