Sparse sampling Kaczmarz–Motzkin method with linear convergence
- 2 December 2021
- journal article
- research article
- Published by Wiley in Mathematical Methods in the Applied Sciences
- Vol. 45 (7) , 3463-3478
Abstract
The randomized sparse Kaczmarz method was recently proposed to recover sparse solutions of linear systems. In this work, we introduce a greedy variant of the randomized sparse Kaczmarz method by employing the sampling Kaczmarz–Motzkin method and prove its linear convergence in expectation with respect to the Bregman distance in the noiseless and noisy cases. This greedy variant can be viewed as a unification of the sampling Kaczmarz–Motzkin method and the randomized sparse Kaczmarz method, and hence inherits the merits of these two methods. Numerically, we report a couple of experimental results to demonstrate its superiority.Keywords
All Related Versions
Funding Information
- National Natural Science Foundation of China (11971480, 61977065)
This publication has 14 references indexed in Scilit:
- A dual algorithm for a class of augmented convex signal recovery modelsCommunications in Mathematical Sciences, 2015
- A sparse Kaczmarz solver and a linearized Bregman method for online compressed sensing2014
- Block Kaczmarz Method with InequalitiesJournal of Mathematical Imaging and Vision, 2014
- The Linearized Bregman Method via Split Feasibility Problems: Analysis and GeneralizationsSIAM Journal on Imaging Sciences, 2014
- Paved with good intentions: Analysis of a randomized block Kaczmarz methodLinear Algebra and its Applications, 2014
- Augmented $\ell_1$ and Nuclear-Norm Models with a Globally Linearly Convergent AlgorithmSIAM Journal on Imaging Sciences, 2013
- Acceleration of randomized Kaczmarz method via the Johnson–Lindenstrauss LemmaNumerical Algorithms, 2011
- Randomized Methods for Linear Constraints: Convergence Rates and ConditioningMathematics of Operations Research, 2010
- A Randomized Kaczmarz Algorithm with Exponential ConvergenceJournal of Fourier Analysis and Applications, 2008
- The Mathematics of Computerized Tomography (Classics in Applied Mathematics, Vol. 32)Inverse Problems, 2002