  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.
