Randomized Projection Methods for Linear Systems with Arbitrarily Large Sparse Corruptions

DOI10.1137/18M1179213zbMath1436.65031arXiv1803.08114OpenAlexW2982556428WikidataQ126856453 ScholiaQ126856453MaRDI QIDQ5241241

Jamie Haddock, Deanna Needell

Publication date: 30 October 2019

Published in: SIAM Journal on Scientific Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1803.08114

zbMATH Keywords

iterative methodscorrupted linear systemsrandomized projection methods

Mathematics Subject Classification ID

Numerical solutions to overdetermined systems, pseudoinverses (65F20) Ill-posedness and regularization problems in numerical linear algebra (65F22) Iterative numerical methods for linear systems (65F10)

Related Items

On block accelerations of quantile randomized Kaczmarz for corrupted systems of linear equations, Quantile-Based Iterative Methods for Corrupted Systems of Linear Equations, Approximate Solutions of Linear Systems at a Universal Rate, Randomized Extended Average Block Kaczmarz for Solving Least Squares, Convergence analyses based on frequency decomposition for the randomized row iterative method, Greed Works: An Improved Analysis of Sampling Kaczmarz--Motzkin, A Kaczmarz Algorithm for Solving Tree Based Distributed Systems of Equations

Uses Software

• Regularization tools
• UCI-ml

Cites Work

• Unnamed Item
• A mathematical introduction to compressive sensing
• Acceleration of randomized Kaczmarz method via the Johnson-Lindenstrauss lemma
• Approximating maximum satisfiable subsystems of linear equations of bounded width
• Randomized Kaczmarz solver for noisy linear systems
• A randomized Kaczmarz algorithm with exponential convergence
• Strong underrelaxation in Kaczmarz's method for inconsistent systems
• Misclassification minimization
• The complexity and approximability of finding maximum feasible subsystems of linear relations
• Hildreth's algorithm with applications to soft constraints for user interface layout
• Paved with good intentions: analysis of a randomized block Kaczmarz method
• Regularization tools version \(4.0\) for matlab \(7.3\)
• The Mathematics of Computerized Tomography
• Randomized Extended Kaczmarz for Solving Least Squares
• Fast Heuristics for the Maximum Feasible Subsystem Problem
• Randomized Methods for Linear Constraints: Convergence Rates and Conditioning
• Randomized Iterative Methods for Linear Systems
• Randomized Relaxation Methods for the Maximum Feasible Subsystem Problem
• Branch-and-Cut for the Maximum Feasible Subsystem Problem
• Relaxation methods for image reconstruction
• A Sampling Kaczmarz--Motzkin Algorithm for Linear Feasibility