Extended randomized Kaczmarz method for sparse least squares and impulsive noise problems
From MaRDI portal
Publication:2168919
Abstract: The Extended Randomized Kaczmarz method is a well known iterative scheme which can find the Moore-Penrose inverse solution of a possibly inconsistent linear system and requires only one additional column of the system matrix in each iteration in comparison with the standard randomized Kaczmarz method. Also, the Sparse Randomized Kaczmarz method has been shown to converge linearly to a sparse solution of a consistent linear system. Here, we combine both ideas and propose an Extended Sparse Randomized Kaczmarz method. We show linear expected convergence to a sparse least squares solution in the sense that an extended variant of the regularized basis pursuit problem is solved. Moreover, we generalize the additional step in the method and prove convergence to a more abstract optimization problem. We demonstrate numerically that our method can find sparse least squares solutions of real and complex systems if the noise is concentrated in the complement of the range of the system matrix and that our generalization can handle impulsive noise.
Recommendations
- Randomized extended Kaczmarz for solving least squares
- On partially randomized extended Kaczmarz method for solving large sparse overdetermined inconsistent linear systems
- Single projection Kaczmarz extended algorithms
- A weighted randomized sparse Kaczmarz method for solving linear systems
- Randomized block Kaczmarz method with projection for solving least squares
Cites work
- A randomized Kaczmarz algorithm with exponential convergence
- A Singular Value Thresholding Algorithm for Matrix Completion
- Accelerating Sparse Recovery by Reducing Chatter
- Alternating direction algorithms for \(\ell_1\)-problems in compressive sensing
- Analysis and generalizations of the linearized Bregman method
- Augmented _1 and nuclear-norm models with a globally linearly convergent algorithm
- Compressed sensing
- Convergence of the linearized Bregman iteration for \(\ell _1\)-norm minimization
- Efficiency of coordinate descent methods on huge-scale optimization problems
- Exact regularization of polyhedral norms
- First order algorithms in variational image processing
- For most large underdetermined systems of linear equations the minimal đ1ânorm solution is also the sparsest solution
- Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization
- scientific article; zbMATH DE number 3296905 (Why is no real title available?)
- Linear convergence of descent methods for the unconstrained minimization of restricted strongly convex functions
- Linear convergence of the randomized sparse Kaczmarz method
- On the Reconstruction of Block-Sparse Signals With an Optimal Number of Measurements
- On two-subspace randomized extended Kaczmarz method for solving large linear least-squares problems
- Parallel random coordinate descent method for composite minimization: convergence analysis and error bounds
- Paved with good intentions: analysis of a randomized block Kaczmarz method
- Randomized double and triple Kaczmarz for solving extended normal equations
- Randomized extended average block Kaczmarz for solving least squares
- Randomized extended Kaczmarz for solving least squares
- Randomized Kaczmarz with averaging
- Randomized sparse block Kaczmarz as randomized dual block-coordinate descent
- Recovery of Sparsely Corrupted Signals
- Regularized Kaczmarz Algorithms for Tensor Recovery
- Robust regression: Asymptotics, conjectures and Monte Carlo
- Robust Sparse Recovery in Impulsive Noise via $\ell _p$ -$\ell _1$ Optimization
- Strong conical hull intersection property, bounded linear regularity, Jameson's property \((G)\), and error bounds in convex optimization
- The linearized Bregman method via split feasibility problems: analysis and generalizations
- The randomized Kaczmarz method with mismatched adjoint
- Tight upper bounds for the convergence of the randomized extended Kaczmarz and Gauss-Seidel algorithms.
Cited in
(20)- A weighted randomized sparse Kaczmarz method for solving linear systems
- Accelerated greedy randomized augmented Kaczmarz algorithm for inconsistent linear systems
- Faster randomized block sparse Kaczmarz by averaging
- On the Convergence of Stochastic Gradient Descent for Linear Inverse Problems in Banach Spaces
- A BregmanâKaczmarz method for nonlinear systems of equations
- 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
- Stochastic iterative methods for online rank aggregation from pairwise comparisons
- A subspace constrained randomized Kaczmarz method for structure or external knowledge exploitation
- 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
- Quantile-RK and double quantile-RK error horizon analysis
- Randomized extended average block Kaczmarz method for inconsistent tensor equations under t-product
- On the randomized multiple row-action methods for solving linear least-squares problems
- A fast Bregman projection method for linearly constrained optimization problems
- Minimal error momentum Bregman-Kaczmarz
- Surrogate hyperplane regularized iterative methods for sparse and structured solutions of factorized linear systems
- Relaxed greedy randomized Kaczmarz with signal averaging for solving doubly-noisy linear systems
- A Unified Framework for Randomized Row-Action Methods for Structured Data Fitting and Constraint Geometry
This page was built for publication: Extended randomized Kaczmarz method for sparse least squares and impulsive noise problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2168919)
