Quantile-based iterative methods for corrupted systems of linear equations
From MaRDI portal
Abstract: Often in applications ranging from medical imaging and sensor networks to error correction and data science (and beyond), one needs to solve large-scale linear systems in which a fraction of the measurements have been corrupted. We consider solving such large-scale systems of linear equations that are inconsistent due to corruptions in the measurement vector . We develop several variants of iterative methods that converge to the solution of the uncorrupted system of equations, even in the presence of large corruptions. These methods make use of a quantile of the absolute values of the residual vector in determining the iterate update. We present both theoretical and empirical results that demonstrate the promise of these iterative approaches.
Recommendations
- Randomized Projection Methods for Linear Systems with Arbitrarily Large Sparse Corruptions
- Quantile-based Random Kaczmarz for corrupted linear systems of equations
- Randomized Kaczmarz solver for noisy linear systems
- Parsimonious least norm approximation
- On relaxed greedy randomized augmented Kaczmarz methods for solving large sparse inconsistent linear systems
Cites work
- scientific article; zbMATH DE number 4001918 (Why is no real title available?)
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- A Stochastic Approximation Method
- A fast Kaczmarz-Kovarik algorithm for consistent least-squares problems
- A mathematical introduction to compressive sensing
- A new descent algorithm for the least absolute value regression problem
- A randomized Kaczmarz algorithm with exponential convergence
- A sampling Kaczmarz-Motzkin algorithm for linear feasibility
- Accelerated sampling Kaczmarz Motzkin algorithm for the linear feasibility problem
- Algorithms for unconstrained \(L_ 1\) simple linear regression
- Almost sure convergence of the Kaczmarz algorithm with random measurements
- An Improved Algorithm for Discrete l₁ Linear Approximation
- An Iterative Technique for Absolute Deviations Curve Fitting
- Block-iterative methods for consistent and inconsistent linear equations
- Block-projections algorithms with blocks containing mutually orthogonal rows and columns
- Decoding by Linear Programming
- Dense Error Correction Via \ell^1-Minimization
- Greed Works: An Improved Analysis of Sampling Kaczmarz--Motzkin
- High-dimensional probability. An introduction with applications in data science
- Hildreth's algorithm with applications to soft constraints for user interface layout
- Incorporation of a priori moment information into signal recovery and synthesis problems
- Iterative algorithms for large partitioned linear systems, with applications to image reconstruction
- Large-scale machine learning with stochastic gradient descent
- Least Absolute Deviations Curve-Fitting
- Median-truncated gradient descent: a robust and scalable nonconvex approach for signal estimation
- Non-convex low-rank matrix recovery with arbitrary outliers via median-truncated gradient descent
- On Motzkin's method for inconsistent linear systems
- On block Gaussian sketching for the Kaczmarz method
- On greedy randomized Kaczmarz method for solving large sparse linear systems
- On relaxed greedy randomized Kaczmarz methods for solving large sparse linear systems
- On the acceleration of Kaczmarz's method for inconsistent linear systems
- Optimal distributed online prediction using mini-batches
- Optimization methods for large-scale machine learning
- Paved with good intentions: analysis of a randomized block Kaczmarz method
- Randomized Kaczmarz solver for noisy linear systems
- Randomized Projection Methods for Linear Systems with Arbitrarily Large Sparse Corruptions
- Randomized Relaxation Methods for the Maximum Feasible Subsystem Problem
- Randomized extended Kaczmarz for solving least squares
- Randomized extended average block Kaczmarz for solving least squares
- Regularization tools version 4.0 for matlab 7.3
- Revisiting Randomized Gossip Algorithms: General Framework, Convergence Rates and Novel Block and Accelerated Protocols
- Row-Action Methods for Huge and Sparse Systems and Their Applications
- Single projection Kaczmarz extended algorithms
- Small ball probabilities for linear images of high-dimensional distributions
- Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm
- Strong underrelaxation in Kaczmarz's method for inconsistent systems
- The Relaxation Method for Linear Inequalities
- The Relaxation Method for Linear Inequalities
- The complexity and approximability of finding maximum feasible subsystems of linear relations
Cited in
(19)- Randomized Kaczmarz in adversarial distributed setting
- Solving, tracking and stopping streaming linear inverse problems
- Stochastic gradient descent for streaming linear and rectified linear systems with adversarial corruptions
- A block coordinate descent linear least squares solver by quantile statistics
- Stochastic iterative methods for online rank aggregation from pairwise comparisons
- A subspace constrained randomized Kaczmarz method for structure or external knowledge exploitation
- Quantile-based Random Kaczmarz for corrupted linear systems of equations
- Adaptive Bregman-Kaczmarz: an approach to solve linear inverse problems with independent noise exactly
- Quantile-based random sparse Kaczmarz for corrupted and noisy linear systems
- Randomized iterative methods for tensor regression under the t-product
- Approximate Solutions of Linear Systems at a Universal Rate
- Quantile-RK and double quantile-RK error horizon analysis
- A quantile-based block Kaczmarz algorithm for solving large consistent linear systems
- Randomized Kaczmarz methods for t-product tensor linear systems with factorized operators
- Randomized Kaczmarz with geometrically smoothed momentum
- On block accelerations of quantile randomized Kaczmarz for corrupted systems of linear equations
- On the randomized multiple row-action methods for solving linear least-squares problems
- Linear convergence of reshuffling Kaczmarz methods with sparse constraints
- Kaczmarz Kac walk
This page was built for publication: Quantile-based iterative methods for corrupted systems of linear equations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5071437)
