@article{01dd04ac668c4cc180ffef37ff4f6a62,
title = "QUANTILE-BASED ITERATIVE METHODS FOR CORRUPTED SYSTEMS OF LINEAR EQUATIONS",
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.",
keywords = "Kaczmarz method, corrupted linear systems, least squares problems, quantile methods, stochastic iterative methods",
author = "Jamie Haddock and Deanna Needell and Elizaveta Rebrova and William Swartworth",
note = "Funding Information: \ast Received by the editors June 25, 2021; accepted for publication (in revised form) by M. Tygert December 23, 2021; published electronically April 13, 2022. https://doi.org/10.1137/21M1429187 Funding: The work of the authors was partially supported by National Science Foundation (NSF) grants 2011140 and BIGDATA 1740325. The work of the first author was also partially supported by NSF grant DMS-2111440. \dagger Department of Mathematics, Harvey Mudd College, Claremont, CA 91711 USA (jhaddock@ g.hmc.edu). \ddagger Department of Mathematics, University of California, Los Angeles, Los Angeles, CA 90095 USA (deanna@math.ucla.edu, wswartworth@math.ucla.edu). \S Department of Operations Research and Financial Engineering (ORFE), Princeton University, Princeton, NJ 08540 USA (elre@princeton.edu). Publisher Copyright: {\textcopyright} 2022 Society for Industrial and Applied Mathematics",
year = "2022",
doi = "10.1137/21M1429187",
language = "English (US)",
volume = "43",
pages = "605--637",
journal = "SIAM Journal on Matrix Analysis and Applications",
issn = "0895-4798",
publisher = "Society for Industrial and Applied Mathematics Publications",
number = "2",
}