On Subsampled Quantile Randomized Kaczmarz

Jamie Haddock, Anna Ma, Elizaveta Rebrova

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

When solving noisy linear systems Ax = b + c, the theoretical and empirical performance of stochastic iterative methods, such as the Randomized Kaczmarz algorithm, depends on the noise level. However, if there are a small number of highly corrupt measurements, one can instead use quantile-based methods to guarantee convergence to the solution x of the system, despite the presence of noise. Such methods require the computation of the entire residual vector, which may not be desirable or even feasible in some cases. In this work, we analyze the sub-sampled quantile Randomized Kaczmarz (sQRK) algorithm for solving large-scale linear systems which utilize a sub-sampled residual to approximate the quantile threshold. We prove that this method converges to the unique solution to the linear system and provide numerical experiments that support our theoretical findings. We additionally remark on the extremely small sample size case and demonstrate the importance of interplay between the choice of quantile and subset size.

Original languageEnglish (US)
Title of host publication2023 59th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2023
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9798350328141
DOIs
StatePublished - 2023
Event59th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2023 - Monticello, United States
Duration: Sep 26 2023Sep 29 2023

Publication series

Name2023 59th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2023

Conference

Conference59th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2023
Country/TerritoryUnited States
CityMonticello
Period9/26/239/29/23

All Science Journal Classification (ASJC) codes

  • Artificial Intelligence
  • Computational Theory and Mathematics
  • Computer Networks and Communications
  • Computer Science Applications
  • Computational Mathematics
  • Control and Optimization

Fingerprint

Dive into the research topics of 'On Subsampled Quantile Randomized Kaczmarz'. Together they form a unique fingerprint.

Cite this