QUANTILE-BASED ITERATIVE METHODS FOR CORRUPTED SYSTEMS OF LINEAR EQUATIONS

Jamie Haddock, Deanna Needell, Elizaveta Rebrova, William Swartworth

Research output: Contribution to journalArticlepeer-review

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 Ax = b that are inconsistent due to corruptions in the measurement vector b. 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.

Original languageEnglish (US)
Pages (from-to)605-637
Number of pages33
JournalSIAM Journal on Matrix Analysis and Applications
Volume43
Issue number2
DOIs
StatePublished - 2022

All Science Journal Classification (ASJC) codes

  • Analysis

Keywords

  • corrupted linear systems
  • Kaczmarz method
  • least squares problems
  • quantile methods
  • stochastic iterative methods

Fingerprint

Dive into the research topics of 'QUANTILE-BASED ITERATIVE METHODS FOR CORRUPTED SYSTEMS OF LINEAR EQUATIONS'. Together they form a unique fingerprint.

Cite this