# A Note on Randomized Kaczmarz Algorithm for Solving Doubly-Noisy Linear Systems

arXiv: https://arxiv.org/abs/2308.16904 · HTML: https://mlsanity.com/paper/2308.16904/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 45 references that are in the map.
- First posted on arXiv 31 Aug 2023.

## Builds on (most cited first, 8 of 8)

- [Phase Retrieval via Randomized Kaczmarz: Theoretical Guarantees](https://mlsanity.com/paper/1706.09993/) (2017)
- [Faster randomized block Kaczmarz algorithms](https://mlsanity.com/paper/1902.09946/) (2019)
- [A sparse Kaczmarz solver and a linearized Bregman method for online compressed sensing](https://mlsanity.com/paper/1403.7543/) (2014)
- [Linear convergence of the Randomized Sparse Kaczmarz Method](https://mlsanity.com/paper/1610.02889/) (2016)
- [Online and Batch Supervised Background Estimation via L1 Regression](https://mlsanity.com/paper/1712.02249/) (2017)
- [On the Convergence Analysis of Asynchronous SGD for Solving Consistent Linear Systems](https://mlsanity.com/paper/2004.02163/) (2020)
- [Weighted Low Rank Approximation for Background Estimation Problems](https://mlsanity.com/paper/1707.01753/) (2017)
- [Convergence of the randomized Kaczmarz method for phase retrieval](https://mlsanity.com/paper/1706.10291/) (2017)

## Built on by (most cited first, 1 of 1)

- [Where Have All the Kaczmarz Iterates Gone?](https://mlsanity.com/paper/2510.08563/) (2025)

## Abstract (arXiv)

Large-scale linear systems, Ax=b, frequently arise in practice and demand effective iterative solvers. Often, these systems are noisy due to operational errors or faulty data-collection processes. In the past decade, the randomized Kaczmarz (RK) algorithm has been studied extensively as an efficient iterative solver for such systems. However, the convergence study of RK in the noisy regime is limited and considers measurement noise in the right-hand side vector, b. Unfortunately, in practice, that is not always the case; the coefficient matrix A can also be noisy. In this paper, we analyze the convergence of RK for textitdoubly-noisy linear systems, i.e., when the coefficient matrix, A, has additive or multiplicative noise, and b is also noisy. In our analyses, the quantity tilde R=| tilde Adagger |2 |tilde A |F2 influences the convergence of RK, where tilde A represents a noisy version of A. We claim that our analysis is robust and realistically applicable, as we do not require information about the noiseless coefficient matrix, A, and considering different conditions on noise, we can control the convergence of RK. We perform numerical experiments to substantiate our theoretical findings.