A Weighted Randomized Sparse Kaczmarz Method for Solving Linear Systems

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 $\Vert a_i{\Vert }_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 $|⟨a_i,x_k⟩-b_i{|}^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.

arXiv commentDr. Lionel N. Tondji kindly reminded us that their 2021 conference paper shares some similarity with ours. We feel very sorry that we had not noticed their work before we submitted our paper. Here, we claim that the method was independently proposed by both of us. Moreover, we also consider an exact step-size version and the effect of the weighted parameter with detailed theory

References in corpus (6)

• Randomized Extended Kaczmarz for Solving Least-Squares
• Randomized Kaczmarz solver for noisy linear systems
• Adaptively Sketched Bregman Projection Methods for Linear Systems
• A Kaczmarz Method with Simple Random Sampling for Solving Large Linear Systems
• Sparse Sampling Kaczmarz-Motzkin Method with Linear Convergence
• Randomized regularized extended Kaczmarz algorithms for tensor recovery