Faster randomized block sparse Kaczmarz by averaging
From MaRDI portal
Abstract: The standard randomized sparse Kaczmarz (RSK) method is an algorithm to compute sparse solutions of linear systems of equations and uses sequential updates, and thus, does not take advantage of parallel computations. In this work, we introduce a parallel (mini batch) version of RSK based on averaging several Kaczmarz steps. Naturally, this method allows for parallelization and we show that it can also leverage large over-relaxation. We prove linear expected convergence and show that, given that parallel computations can be exploited, the method provably provides faster convergence than the standard method. This method can also be viewed as a variant of the linearized Bregman algorithm, a randomized dual block coordinate descent update, a stochastic mirror descent update, or a relaxed version of RSK and we recover the standard RSK method when the batch size is equal to one. We also provide estimates for inconsistent systems and show that the iterates convergence to an error in the order of the noise level. Finally, numerical examples illustrate the benefits of the new algorithm.
Recommendations
Cites work
- A randomized Kaczmarz algorithm with exponential convergence
- Analysis and generalizations of the linearized Bregman method
- Atomic Decomposition by Basis Pursuit
- Compressed sensing
- Compressive sampling
- Convergence of the linearized Bregman iteration for \(\ell _1\)-norm minimization
- Convergence rates for Kaczmarz-type algorithms
- Efficiency of coordinate descent methods on huge-scale optimization problems
- Exact Regularization of Convex Programs
- Extended randomized Kaczmarz method for sparse least squares and impulsive noise problems
- Faster randomized block Kaczmarz algorithms
- scientific article; zbMATH DE number 3790208 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 635657 (Why is no real title available?)
- Improved analysis of the subsampled randomized Hadamard transform
- Iterative methods for linear systems. Theory and applications
- Linear convergence of the randomized sparse Kaczmarz method
- Linearized Bregman iterations for compressed sensing
- Methods of conjugate gradients for solving linear systems
- Mirror descent and nonlinear projected subgradient methods for convex optimization.
- Nonasymptotic convergence of stochastic proximal point methods for constrained convex optimization
- On Adaptive Sketch-and-Project for Solving Linear Systems
- On greedy randomized average block Kaczmarz method for solving large linear systems
- On stochastic Kaczmarz type methods for solving large scale systems of ill-posed equations
- On the acceleration of Kaczmarz's method for inconsistent linear systems
- Parallel coordinate descent methods for big data optimization
- Paved with good intentions: analysis of a randomized block Kaczmarz method
- Preasymptotic convergence of randomized Kaczmarz method
- Randomized extended average block Kaczmarz for solving least squares
- Randomized extended Kaczmarz for solving least squares
- Randomized Kaczmarz solver for noisy linear systems
- Randomized Kaczmarz with averaging
- Randomized sparse block Kaczmarz as randomized dual block-coordinate descent
- Relaxation methods for image reconstruction
- Robust Stochastic Approximation Approach to Stochastic Programming
- Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
- Sparse nonnegative solution of underdetermined linear equations by linear programming
- Stochastic mirror descent dynamics and their convergence in monotone variational inequalities
- Stochastic reformulations of linear systems: algorithms and convergence theory
- The linearized Bregman method via split feasibility problems: analysis and generalizations
- Validation analysis of mirror descent stochastic approximation method
Cited in
(17)- Randomized Kaczmarz with averaging
- Randomized sparse block Kaczmarz as randomized dual block-coordinate descent
- Faster randomized block Kaczmarz algorithms
- Stochastic mirror descent method for linear ill-posed problems in Banach spaces
- A greedy average block sparse Kaczmarz method for sparse solutions of linear systems
- A randomized sparse Kaczmarz solver for sparse signal recovery via minimax-concave penalty
- On greedy randomized Kaczmarz-type methods for solving the system of tensor equations
- The sparse Kaczmarz method with surrogate hyperplane for the regularized basis pursuit problem
- Adaptive Bregman-Kaczmarz: an approach to solve linear inverse problems with independent noise exactly
- Acceleration and restart for the randomized Bregman-Kaczmarz method
- A surrogate hyperplane Bregman-Kaczmarz method for solving linear inverse problems
- On weighted average fast block Kaczmarz methods for solving large consistent linear systems
- Greedy randomized Kaczmarz with momentum method for nonlinear equation
- A fast block nonlinear Bregman-Kaczmarz method with averaging for nonlinear sparse signal recovery
- A guide to stochastic optimisation for large-scale inverse problems
- Quantile-based random sparse Kaczmarz for corrupted and noisy linear systems
- On greedy randomized average block sparse Kaczmarz method for solving sparse solutions to linear problems
This page was built for publication: Faster randomized block sparse Kaczmarz by averaging
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6109882)
