  The standard randomized sparse Kaczmarz (RSK) method is an algorithm to
compute sparse solutions of linear systems of equations and uses sequential
updates, and thus, does not take advantage of parallel computations. In this
work, we introduce a parallel (mini batch) version of RSK based on averaging
several Kaczmarz steps. Naturally, this method allows for parallelization and
we show that it can also leverage large over-relaxation. We prove linear
expected convergence and show that, given that parallel computations can be
exploited, the method provably provides faster convergence than the standard
method. This method can also be viewed as a variant of the linearized Bregman
algorithm, a randomized dual block coordinate descent update, a stochastic
mirror descent update, or a relaxed version of RSK and we recover the standard
RSK method when the batch size is equal to one. We also provide estimates for
inconsistent systems and show that the iterates convergence to an error in the
order of the noise level. Finally, numerical examples illustrate the benefits
of the new algorithm.
