Weighted Randomized Kaczmarz for Sparsely Corrupted Linear Systems
Abstract
In this paper, we introduce a generalized weighted randomized Kaczmarz framework to approximate solutions to overdetermined linear systems whose measurements are perturbed by sparse, additive corruptions. The proposed framework samples equations with probabilities proportional to a user-defined weighting function of their corresponding residual magnitudes. Our work focuses on weighting functions that will reduce the influence of potentially corrupted equations, and provides analyses for a general class of non-increasing weighting functions. We derive one-step expected squared error bounds that separate progress on uncorrupted equations from the contribution of corrupted equations, and provide sufficient conditions for geometric convergence under one specific family of weighting functions -- threshold weighting. We also investigate adaptive exponential weights scaled by the median or median absolute deviation of residual magnitudes, requiring no prior knowledge of the corruption fraction or magnitudes. Lastly, we consider a family of inverse residual weighting functions. Numerical experiments demonstrate the benefit of such a generalized framework in its flexibility in developing approaches for settings in which information about the corruptions is known or unknown.
Related
- On Convergence Behavior of Randomized Kaczmarz-type Methods for Solving Doubly Noisy Linear Systems
- Quantile Randomized Kaczmarz for Streaming Linear Systems with Massart Noise
- Efficient variance reduction for randomized Kaczmarz methods via residual-tracking control variates
- Variational Bayesian Data Detection for Multiuser MIMO Systems Corrupted by Phase Noises
- A greedy double-block nonlinear Bregman-Kaczmarz method for nonlinear equations
BibTeX
@misc{chen2026weighted,
title = {{Weighted Randomized Kaczmarz for Sparsely Corrupted Linear Systems}},
author = {Jessie Chen and Ziyu Cheng and Yunhui He and Alona Kryshchenko and Jocelyn T. Chi and Anna Ma and Jamie Haddock},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.03889},
eprint = {2611.03889},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.03889},
}
RIS
TY - UNPB
TI - Weighted Randomized Kaczmarz for Sparsely Corrupted Linear Systems
AU - Jessie Chen
AU - Ziyu Cheng
AU - Yunhui He
AU - Alona Kryshchenko
AU - Jocelyn T. Chi
AU - Anna Ma
AU - Jamie Haddock
PY - 2026
DA - 2026/11/02
PB - arXiv
DO - 10.48550/arxiv.2611.03889
UR - https://arxiv.org/abs/2611.03889
AB - In this paper, we introduce a generalized weighted randomized Kaczmarz framework to approximate solutions to overdetermined linear systems whose measurements are perturbed by sparse, additive corruptions. The proposed framework samples equations with probabilities proportional to a user-defined weighting function of their corresponding residual magnitudes. Our work focuses on weighting functions that will reduce the influence of potentially corrupted equations, and provides analyses for a general class of non-increasing weighting functions. We derive one-step expected squared error bounds that separate progress on uncorrupted equations from the contribution of corrupted equations, and provide sufficient conditions for geometric convergence under one specific family of weighting functions -- threshold weighting. We also investigate adaptive exponential weights scaled by the median or median absolute deviation of residual magnitudes, requiring no prior knowledge of the corruption fraction or magnitudes. Lastly, we consider a family of inverse residual weighting functions. Numerical experiments demonstrate the benefit of such a generalized framework in its flexibility in developing approaches for settings in which information about the corruptions is known or unknown.
ER -