On Convergence Behavior of Randomized Kaczmarz-type Methods for Solving Doubly Noisy Linear Systems
Abstract
In this paper, we consider the convergence of some popular Kaczmarz-type methods, including the randomized Kaczmarz (RK) method, the randomized extended Kaczmarz (REK) method, the randomized block Kaczmarz (RBK) method, and the randomized double block Kaczmarz (RDBK) method for doubly noisy linear system. To the best of our knowledge, this is the first work that considers and compares the convergence of the Kaczmarz-type methods for consistent linear systems, as well as that for inconsistent linear systems to solve double noisy linear system. We prove that these methods converge to a neighborhood of the smallest norm least squares solution of the underlying noiseless system. Specifically, RK and RBK that are designed for consistent linear systems, often outperform REK and RDBK that are designed for inconsistent linear systems, respectively, in terms of the convergence rate or the convergence horizon. Moreover, we establish the convergence of the more general sketch-and-project framework for the doubly noisy linear system. The analysis provides more comprehensive results without imposing any additional restrictions. Numerical experiments are performed to validate our theoretical results.
Related
- Efficient variance reduction for randomized Kaczmarz methods via residual-tracking control variates
- On randomized batch-sampling coordinate descent methods for solving linear least-squares problems
- Tight Convergence Bounds for the Classical Kaczmarz Method
- Asynchronous Jacobi and randomized Gauss--Seidel methods in shared and distributed memory: A unified convergence-rate analysis
- Weighted Randomized Kaczmarz for Sparsely Corrupted Linear Systems
BibTeX
@misc{gan2026convergence,
title = {{On Convergence Behavior of Randomized Kaczmarz-type Methods for Solving Doubly Noisy Linear Systems}},
author = {Yudan Gan and Gang Wu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2608.22259},
eprint = {2608.22259},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.22259},
}
RIS
TY - UNPB
TI - On Convergence Behavior of Randomized Kaczmarz-type Methods for Solving Doubly Noisy Linear Systems
AU - Yudan Gan
AU - Gang Wu
PY - 2026
DA - 2026/10/08
PB - arXiv
DO - 10.48550/arxiv.2608.22259
UR - https://arxiv.org/abs/2608.22259
AB - In this paper, we consider the convergence of some popular Kaczmarz-type methods, including the randomized Kaczmarz (RK) method, the randomized extended Kaczmarz (REK) method, the randomized block Kaczmarz (RBK) method, and the randomized double block Kaczmarz (RDBK) method for doubly noisy linear system. To the best of our knowledge, this is the first work that considers and compares the convergence of the Kaczmarz-type methods for consistent linear systems, as well as that for inconsistent linear systems to solve double noisy linear system. We prove that these methods converge to a neighborhood of the smallest norm least squares solution of the underlying noiseless system. Specifically, RK and RBK that are designed for consistent linear systems, often outperform REK and RDBK that are designed for inconsistent linear systems, respectively, in terms of the convergence rate or the convergence horizon. Moreover, we establish the convergence of the more general sketch-and-project framework for the doubly noisy linear system. The analysis provides more comprehensive results without imposing any additional restrictions. Numerical experiments are performed to validate our theoretical results.
ER -