A Weighted Randomized Sparse Kaczmarz Method for Solving Linear Systems

DOI10.1007/S40314-022-02105-9MaRDI QIDQ6439974arXivFDO

Authors Lu Zhang, Ziyang Yuan, Hongxia Wang, Hui Zhang

Publication date 11 June 2023

Published in arXiv

Full work available at URL https://doi.org/10.1007/S40314-022-02105-9

Mathematics Subject Classification ID

Iterative numerical methods for linear systems (65F10) Numerical optimization and variational techniques (65K10)

arXiv classification

cs.NAmath.NAmath.OC

Abstract: The randomized sparse Kaczmarz method, designed for seeking the sparse solutions of the linear systems $Ax=b$, selects the $i$-th projection hyperplane with likelihood proportional to $|a_i{|}_2^2$, where $a_i^T$ is $i$-th row of $A$. In this work, we propose a weighted randomized sparse Kaczmarz method, which selects the $i$-th projection hyperplane with probability proportional to $lvertlangle{a}_i,x_{k}angle-b_{i}ver{t}^p$, where $0<p<infty$, for possible acceleration. It bridges the randomized Kaczmarz and greedy Kaczmarz by parameter $p$. Theoretically, we show its linear convergence rate in expectation with respect to the Bregman distance in the noiseless and noisy cases, which is at least as efficient as the randomized sparse Kaczmarz method. The superiority of the proposed method is demonstrated via a group of numerical experiments.

This page was built for publication: A Weighted Randomized Sparse Kaczmarz Method for Solving Linear Systems

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