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

El Houcine Bergou, Soumia Boucherouite, Aritra Dutta, Xin Li, Anna Ma

Abstract

The Randomized Kaczmarz (RK) algorithm is a widely utilized iterative method for solving large-scale linear systems due to its efficiency and simplicity. However, traditional convergence analysis typically assumes a noise-free coefficient matrix $A$, focusing solely on measurement noise in the observation vector $b$. This paper examines the performance of RK in "doubly-noisy" environments where both $A$ and $b$ are subject to perturbations. We provide a robust convergence analysis that establishes a predictable error horizon without requiring restrictive assumptions such as rank-preservation or prior knowledge of the noiseless system.

1. Introduction

In the landscape of numerical linear algebra, the Randomized Kaczmarz (RK) algorithm has emerged as a cornerstone for solving massive systems of equations, $Ax = b$. By iteratively projecting estimates onto randomly selected rows of the matrix, RK achieves high efficiency in high-dimensional spaces. While the algorithm's behavior under measurement noise (errors in $b$) is well-documented, real-world applications—ranging from computed tomography (CT) to seismic imaging—frequently involve "doubly-noisy" systems. In these scenarios, the model matrix $A$ is also corrupted by noise due to modeling inaccuracies or data collection errors.

Existing theoretical frameworks often rely on perturbation analysis of the Moore-Penrose inverse, which typically requires the noise to be sufficiently small so as not to alter the rank of the matrix. Such conditions are rarely met in ill-conditioned, real-world problems. This paper addresses this gap by providing a direct convergence analysis of RK applied to corrupted data.

2. Problem Formulation and Methodology

The study analyzes the standard RK iteration applied to noisy versions of the system components, $\tilde{A}$ and $\tilde{b}$:

$$x_{k+1} = x_k - \frac{\tilde{a}_{i(k)}^\top x_k - \tilde{b}_{i(k)}}{\|\tilde{a}_{i(k)}\|^2} \tilde{a}_{i(k)}$$

where $i(k)$ is chosen with probability proportional to the squared norm of the $i$-th row of $\tilde{A}$. The authors investigate two primary noise models:

  1. Additive Noise: $\tilde{A} = A + E$ and $\tilde{b} = b + \epsilon$.
  2. Multiplicative Noise: $\tilde{A} = (I_m + E)A(I_n + F)$.

The core theoretical contribution is Theorem 3.1, which derives a convergence bound for the expected error $\mathbb{E}[\|x_k - x^*\|^2]$. Unlike classical approaches, this method bypasses the need for the noisy system to be consistent or for the noise $E$ to be infinitesimal, allowing for a more realistic assessment of the algorithm's limits.

3. Key Insights: The Convergence Horizon

A central finding of this research is that in the presence of double noise, RK does not converge to the exact solution $x^*$. Instead, it approaches a "convergence horizon"—a residual error floor. The radius of this error ball is determined by the noise magnitude and the smallest singular value of the noisy matrix $\tilde{A}$.

3.1 Robustness to Rank Fluctuations

Because the analysis focuses directly on the iteration step rather than the global properties of the inverse matrix, the results remain valid even if the noise $E$ changes the rank of $A$. This makes the proposed bounds significantly more robust than those derived from general perturbation theory.

3.2 Noise as a Convergence Catalyst

In a counterintuitive observation, the authors note that injecting a controlled amount of noise can sometimes improve the initial convergence rate. This occurs because noise can improve the scaled condition number of the system. While this leads to a higher eventual error floor, it suggests a potential hybrid strategy: utilizing noisy, fast iterations to reach the vicinity of a solution before switching to cleaner data for final precision.

4. Numerical Validation

The authors validated their theoretical bounds using synthetic consistent linear systems (dimensions up to $m=500, n=300$) generated via Singular Value Decomposition (SVD). The experiments confirmed several key behaviors:

  • Bound Tightness: Theorem 3.1 provides a tighter and more realistic convergence horizon compared to traditional perturbation-based bounds.
  • Noise Sensitivity: As the noise magnitudes ($\sigma_A, \sigma_b$) increase, the slope of the error curve often becomes steeper (faster initial convergence), but the "floor" where the error levels off rises accordingly.
  • Multiplicative Dynamics: In multiplicative noise scenarios, noise originating from the right-hand side ($F$) was found to be a particularly dominant factor in determining the final error horizon.

5. Conclusion and Future Directions

This work provides a necessary extension of Randomized Kaczmarz theory into the realm of doubly-noisy systems. By establishing bounds that do not rely on rank-preservation, the authors offer a more practical tool for predicting RK performance in imperfect data environments.

Future research may extend this analysis to the Randomized Extended Kaczmarz (REK) algorithm, which is designed to handle systems that are inherently inconsistent even before noise is introduced. Additionally, exploring the "noise-injection" phenomenon as a formal preconditioning strategy remains a promising avenue for practical algorithm development.

Summary updated

BibTeX
@article{bergou2024note,
  author = {El Houcine Bergou and Soumia Boucherouite and Aritra Dutta and Xin Li and Anna Ma},
  title = {{A Note on the Randomized Kaczmarz Algorithm for Solving Doubly Noisy Linear Systems}},
  journal = {SIAM J. Matrix Anal. Appl},
  year = {2024},
  doi = {10.1137/23m155712x},
}

Loading related content...

Figure