A fast randomized Kaczmarz algorithm for sparse solutions of consistent\n linear systems

The Kaczmarz algorithm is a popular solver for overdetermined linear systems\ndue to its simplicity and speed. In this paper, we propose a modification that\nspeeds up the convergence of the randomized Kaczmarz algorithm for systems of\nlinear equations with sparse solutions. The speedup is achieved by projecting\nevery iterate onto a weighted row of the linear system while maintaining the\nrandom row selection criteria of Strohmer and Vershynin. The weights are chosen\nto attenuate the contribution of row elements that lie outside of the estimated\nsupport of the sparse solution. While the Kaczmarz algorithm and its variants\ncan only find solutions to overdetermined linear systems, our algorithm\nsurprisingly succeeds in finding sparse solutions to underdetermined linear\nsystems as well. We present empirical studies which demonstrate the\nacceleration in convergence to the sparse solution using this modified approach\nin the overdetermined case. We also demonstrate the sparse recovery\ncapabilities of our approach in the underdetermined case and compare the\nperformance with that of $\\ell_1$ minimization.\n