Georgia Institute of Technology College of Sciences

Randomized Kaczmarz methods — popular special case of the sketch-and-project optimization framework — solve linear systems through iterative projections onto randomly selected equations, resulting in exponential expected convergence via cheap, local updates. While known to be effective in highly overdetermined problems or under the restricted data access, identifying generic scenarios where these methods are advantageous compared to classical Krylov subspace solvers (e.g., Conjugate Gradient, LSQR, GMRES) remained open. In this talk, I will present our recent results demonstrating that properly designed randomized Kaczmarz (sketch-and-project) methods can outperform Krylov methods for both square and rectangular systems complexity-wise. In addition, they are particularly advantageous for approximately low-rank systems common in machine learning (e.g., kernel matrices, signal-plus-noise models) as they quickly capture the large outlying singular values of the linear system. Our approach combines novel spectral analysis of randomly sketched projection matrices with classical numerical analysis techniques, such as including momentum, adaptive regularization, and memoization.