Quantile-based Random Kaczmarz for corrupted linear systems of equations

DOI10.1093/IMAIAI/IAAB029MaRDI QIDQ5878259zbMATH OpenOpenAlexFDO

Authors Stefan Steinerberger

Publication date 20 February 2023

Published in Information and Inference: A Journal of the IMA (Search for Journal in Brave)

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

zbMATH Keywords

corrupted linear systemsKaczmarzstochastic gradient descent

Mathematics Subject Classification ID

Linear equations (linear algebraic aspects) (15A06) Random matrices (algebraic aspects) (15B52) Random matrices (probabilistic aspects) (60B20) Iterative numerical methods for linear systems (65F10)

Abstract: We consider linear systems $Ax=b$ where $Ainmathbb{R}^{mimesn}$ consists of normalized rows, $|a_i{|}_{el{l}^2}=1$, and where up to $$ entries of $b$ have been corrupted (possibly by arbitrarily large numbers). Haddock, Needell, Rebrova and Swartworth propose a quantile-based Random Kaczmarz method and show that for certain random matrices $A$ it converges with high likelihood to the true solution. We prove a deterministic version by constructing, for any matrix $A$, a number $$ such that there is convergence for all perturbations with $$. Assuming a random matrix heuristic, this proves convergence for tall Gaussian matrices with up to $sim0.5\mathrm{\%}$ corruption (a number that can likely be improved).

Recommendations

• Quantile-based iterative methods for corrupted systems of linear equations
• On block accelerations of quantile randomized Kaczmarz for corrupted systems of linear equations
• Randomized Kaczmarz solver for noisy linear systems
• Randomized extended Kaczmarz for solving least squares
• A weighted randomized Kaczmarz method for solving linear systems
• Randomized Kaczmarz method with adaptive stepsizes for inconsistent linear systems
• Randomized Projection Methods for Linear Systems with Arbitrarily Large Sparse Corruptions
• A geometric probability randomized Kaczmarz method for large scale linear systems
• Extension of an error analysis of the randomized Kaczmarz method for inconsistent linear systems
• Randomized methods for rank-deficient linear systems

Cited in

(18)

• On block accelerations of quantile randomized Kaczmarz for corrupted systems of linear equations
• Quantile-based iterative methods for corrupted systems of linear equations
• An Optimal Scheduled Learning Rate for a Randomized Kaczmarz Algorithm
• Approximate Solutions of Linear Systems at a Universal Rate
• 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
• A quantile-based block Kaczmarz algorithm for solving large consistent linear systems
• Randomized Kaczmarz with geometrically smoothed momentum
• Quantile-RK and double quantile-RK error horizon analysis
• Randomized Kaczmarz methods for t-product tensor linear systems with factorized operators
• Kaczmarz Kac walk
• Stochastic gradient descent for streaming linear and rectified linear systems with adversarial corruptions
• A block coordinate descent linear least squares solver by quantile statistics
• Quantile-based random sparse Kaczmarz for corrupted and noisy linear systems
• Randomized iterative methods for tensor regression under the t-product
• On the subsample size of quantile-based randomized Kaczmarz
• Several improved nonlinear deterministic block Kaczmarz methods for solving nonlinear equations
• Quantile-based Loss Filtering for Outlier-Robust Stochastic Gradient Descent

This page was built for publication: Quantile-based Random Kaczmarz for corrupted linear systems of equations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5878259)