Sparse sampling Kaczmarz–Motzkin method with linear convergence

DOI10.1002/MMA.7990zbMATH Open1527.65024arXiv2101.04807OpenAlexW3119500395MaRDI QIDQ6139724FDOQ6139724

Hongxia Wang, Hui Zhang, Ziyang Yuan

Publication date: 19 December 2023

Published in: Mathematical Methods in the Applied Sciences (Search for Journal in Brave)

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

Full work available at URL: https://arxiv.org/abs/2101.04807

zbMATH Keywords

Bregman projectionsampling Kaczmarz-Motzkinsparse Kaczmarz method

Mathematics Subject Classification ID

Numerical solutions to overdetermined systems, pseudoinverses (65F20)

Cites Work

• The university of Florida sparse matrix collection
• A randomized Kaczmarz algorithm with exponential convergence
• The linearized Bregman method via split feasibility problems: analysis and generalizations
• Randomized Methods for Linear Constraints: Convergence Rates and Conditioning
• Paved with good intentions: analysis of a randomized block Kaczmarz method
• Acceleration of randomized Kaczmarz method via the Johnson-Lindenstrauss lemma
• Block Kaczmarz method with inequalities
• Augmented \(\ell_1\) and nuclear-norm models with a globally linearly convergent algorithm
• A dual algorithm for a class of augmented convex signal recovery models
• Linear convergence of the randomized sparse Kaczmarz method

Cited In (4)

• A randomized sparse Kaczmarz solver for sparse signal recovery via minimax-concave penalty
• Adaptively sketched Bregman projection methods for linear systems
• On sampling Kaczmarz-Motzkin methods for solving large-scale nonlinear systems
• Linear convergence of the randomized sparse Kaczmarz method

This page was built for publication: Sparse sampling Kaczmarz–Motzkin method with linear convergence

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6139724)