Linear convergence of the randomized sparse Kaczmarz method (Q1717238)

The Kaczmarz method has been proven to be an efficient tool in computerized tomography. It is used to compute least squares solutions in the case of an overdetermined system \(Ax=b\), i.e., finds minimizers of \(\|Ax-b\|^2\). The authors analyse a randomized variant of the sparse Kaczmarz method to recover sparse solutions of such a linear system. They prove that the iterations of the randomized Kaczmarz method are expected to converge linearly for consistent linear systems, and derive explicit estimates for the rates (Theorem 3.2). Additionally, the authors show that in the noisy/inconsistent case, the iterations reach an error threshold in the order of the noise-level with the same rate as in the noiseless case. The sub-linear convergence rates in expectation for the method of randomized Bregman projections to solve general convex feasibility problems is proven. The algorithms: the randomized sparse Kaczmarz method, the exact-step randomized sparse Kaczmarz method and randomized Bregman projections are described in details. Numerical experiments confirm the theoretical results.