Document Type
Article - postprint
Department
Mathematics (CMC)
Publication Date
11-12-2015
Abstract
The Kaczmarz and Gauss-Seidel methods both solve a linear system Xβ=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.
Rights Information
© 2015, Society for Industrial and Applied Mathematics
DOI
10.1137/15M1014425
Recommended Citation
A. Ma, D. Needell and A. Ramdas. “Convergence Properties of the Randomized Extended Gauss-Seidel and Kaczmarz Methods.” SIAM Journal on Matrix Analysis and Applications, vol. 36, iss. 4, 1590–1604, 2015.
