Linear convergence of reshuffling Kaczmarz methods with sparse constraints
The Kaczmarz method (KZ) is an iterative technique for solving systems of linear equations, originally introduced by \textit{S. Kaczmarz} [Bull. intern. Acad. Polonaise Sci. Lett., Cl. Sci. Math. Nat. A, 355--357 (1937; JFM 63.0524.02)]. It plays a significant role in image and signal processing, where it is commonly known as the algebraic reconstruction technique.\N\NIn contrast, iterative hard thresholding (IHT), as introduced by \textit{T. Blumensath} and \textit{M. E. Davies} [Appl. Comput. Harmon. Anal. 27, No. 3, 265--274 (2009; Zbl 1174.94008)], is a gradient descent method with hard thresholding designed to solve optimization problems arising in compressed sensing.\N\NIn this paper, the authors establish the linear convergence of an accelerated version of IHT based on the Kaczmarz method (KZIHT) for compressed sensing, proposed by \textit{Z. Zhang} et al. [Circuits Syst. Signal Process. 34, No. 6, 2065--2075 (2015; Zbl 1358.94042)], with reshuffling.\N\NThe paper also introduces KZ with periodic thresholding (KZPT), a new method that generalizes KZIHT by applying the thresholding operation periodically -- after a prescribed number of KZ iterations -- and by employing two distinct types of step sizes. In addition to proving linear convergence, the authors show that, with an appropriate choice of thresholding period, KZPT can outperform KZIHT.
- A mathematical introduction to compressive sensing
- A proximal stochastic gradient method with progressive variance reduction
- A randomized Kaczmarz algorithm with exponential convergence
- Acceleration of randomized Kaczmarz method via the Johnson-Lindenstrauss lemma
- Almost sure convergence of the Kaczmarz algorithm with random measurements
- Angenäherte Auflösung von Systemen linearer Gleichungen.
- Compressive sensing and structured random matrices
- Convergence of fixed-point continuation algorithms for matrix rank minimization
- Convergence properties of the randomized extended Gauss-Seidel and Kaczmarz methods
- CoSaMP: Iterative signal recovery from incomplete and inaccurate samples
- Dimensionality reduction with subgaussian matrices: a unified theory
- Efficient online and batch learning using forward backward splitting
- Greedy and randomized versions of the multiplicative Schwarz method
- High-dimensional probability. An introduction with applications in data science
- Iterative hard thresholding based on randomized Kaczmarz method
- Iterative hard thresholding for compressed sensing
- Iterative hard thresholding for low CP-rank tensor models
- Limit laws for random matrix products
- Linear convergence of reshuffling Kaczmarz methods with sparse constraints
- Linear Convergence of Stochastic Iterative Greedy Algorithms With Sparse Constraints
- Low rank tensor recovery via iterative hard thresholding
- Matrix concentration for products
- Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization
- On sparse reconstruction from Fourier and Gaussian measurements
- Optimization for deep learning: an overview
- Paved with good intentions: analysis of a randomized block Kaczmarz method
- Projection method for solving a singular system of linear equations and its applications
- Quantile-based iterative methods for corrupted systems of linear equations
- Randomized Kaczmarz solver for noisy linear systems
- Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
- Row-Action Methods for Huge and Sparse Systems and Their Applications
- Tail bounds via generic chaining
- Why random reshuffling beats stochastic gradient descent
This page was built for publication: Linear convergence of reshuffling Kaczmarz methods with sparse constraints
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6937297)
