A Weighted Randomized Sparse Kaczmarz Method for Solving Linear Systems
Preprint
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 $\lvert\langle a_{i},x_{k}\rangle-b_{i}\rvert^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.
Keywords
All Related Versions
- Version 1, 2023-06-12, ArXiv
- Published version: Computational and Applied Mathematics, 41 (8), 1.
This publication has 20 references indexed in Scilit:
- On randomized partial block Kaczmarz method for solving huge linear algebraic systemsComputational and Applied Mathematics, 2022
- Adaptively sketched Bregman projection methods for linear systemsInverse Problems, 2022
- Sparse sampling Kaczmarz–Motzkin method with linear convergenceMathematical Methods in the Applied Sciences, 2021
- Variational Analysis2021
- A weighted randomized Kaczmarz method for solving linear systemsMathematics of Computation, 2021
- Linear convergence of the randomized sparse Kaczmarz methodMathematical Programming, 2018
- Randomized Kaczmarz solver for noisy linear systemsBIT Numerical Mathematics, 2010
- Sparse and Redundant Representations2010
- A Randomized Kaczmarz Algorithm with Exponential ConvergenceJournal of Fourier Analysis and Applications, 2008
- Introductory Lectures on Convex Optimization2004