A sparse randomized Kaczmarz algorithm

In this paper, we propose a modification that speeds up the convergence of the randomized Kaczmarz algorithm for systems of linear equations with sparse solutions. The speedup is achieved by projecting every iterate onto a weighted row of the linear system while maintaining the random row selection criteria of Strohmer and Vershynin. While the Kaczmarz algorithm and its variants can only find solutions to overdetermined linear systems, our algorithm surprisingly succeeds in finding sparse solutions to underdetermined linear systems as well. Our numerical experiments demonstrate the accelerated convergence in the overdetermined case as well as the sparse recovery capabilities of our approach in the underdetermined case.