Linear convergence of the Randomized Sparse Kaczmarz Method

The randomized version of the Kaczmarz method for the solution of linear systems is known to converge linearly in expectation. In this work we extend this result and show that the recently proposed Randomized Sparse Kaczmarz method for recovery of sparse solutions, as well as many variants, also converges linearly in expectation. The result is achieved in the framework of split feasibility problems and their solution by randomized Bregman projections with respect to strongly convex functions. To obtain the expected convergence rates we prove extensions of error bounds for projections. The convergence result is shown to hold in more general settings involving smooth convex functions, piecewise linear-quadratic functions and also the regularized nuclear norm, which is used in the area of low rank matrix problems. Numerical experiments indicate that the Randomized Sparse Kaczmarz method provides advantages over both the non-randomized and the non-sparse Kaczmarz methods for the solution of over- and under-determined linear systems.