Linear convergence of the Randomized Sparse Kaczmarz Method
arXiv:1610.02889
Abstract
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.
References in corpus (4)
- Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
- Paved with Good Intentions: Analysis of a Randomized Block Kaczmarz Method
- Augmented L1 and Nuclear-Norm Models with a Globally Linearly Convergent Algorithm
- A fast randomized Kaczmarz algorithm for sparse solutions of consistent linear systems