On block Gaussian sketching for the Kaczmarz method

Deanna Needell, Elizaveta Rebrova

Abstract

The Kaczmarz algorithm is one of the most popular methods for solving large-scale over-determined linear systems due to its simplicity and computational efficiency. This method can be viewed as a special instance of a more general class of sketch and project methods. Recently, a block Gaussian version was proposed that uses a block Gaussian sketch, enjoying the regularization properties of Gaussian sketching, combined with the acceleration of the block variants. Theoretical analysis was only provided for the non-block version of the Gaussian sketch method. Here, we provide theoretical guarantees for the block Gaussian Kaczmarz method, proving a number of convergence results showing convergence to the solution exponentially fast in expectation. On the flip side, with this theory and extensive experimental support, we observe that the numerical complexity of each iteration typically makes this method inferior to other iterative projection methods. We highlight only one setting in which it may be advantageous, namely when the regularizing effect is used to reduce variance in the iterates under certain noise models and convergence for some particular matrix constructions.

Introduction

Solving massive, over-determined linear systems ($Ax = b$) is a fundamental challenge in signal processing, optimization, and machine learning. The Kaczmarz method has long been a staple for these problems because of its iterative simplicity: it projects the current estimate onto the solution space of a single equation (or a block of equations) at a time, making it highly memory-efficient.

Recent advancements have generalized the Kaczmarz method into a "sketch and project" framework. Instead of simply selecting a row from the matrix $A$, the algorithm multiplies $A$ by a random "sketch" matrix to create a new projection direction. The Block Gaussian Kaczmarz (BGK) method is a prominent variant that uses a matrix of random Gaussian noise to sketch multiple rows simultaneously. While the 1D (single-row) Gaussian sketch had established theoretical backing, the block version lacked rigorous convergence guarantees until now. This paper fills that theoretical gap and evaluates the method's practical utility against standard iterative solvers.

The Block Gaussian Kaczmarz Method

In a standard block Kaczmarz approach, the algorithm selects a discrete subset of rows from $A$ at each iteration and projects the current solution onto them. In contrast, the BGK method generates a random Gaussian sketch matrix $S$ of size $m \times s$ (where $s$ is the block size). By multiplying the system by $S^T$, the algorithm creates a new block of equations that is a random linear combination of all original equations.

This paper analyzes two primary variants of this approach:

  1. Fresh Sketching: Drawing a completely new Gaussian matrix at every iteration.
  2. Finite Collections: Sampling from a pre-computed finite pool of Gaussian matrices to reduce the overhead of random number generation.

Theoretical Convergence Guarantees

The authors utilize random matrix theory to prove that BGK converges exponentially fast in expectation. For a consistent linear system, the error is shown to shrink by a factor related to the block size and the condition number of the matrix:

$$\mathbb{E}[\|x_{k+1} - x_*\|_2^2] \leq \left(1 - \frac{s}{15m\kappa^2(A)}\right) \|x_k - x_*\|_2^2$$

where $s$ is the block size, $m$ is the number of rows, and $\kappa(A)$ is the condition number. This confirms that mathematically, increasing the block size $s$ directly scales the progress made per iteration. Furthermore, the authors extended these proofs to inconsistent systems ($Ax = b + e$), demonstrating that BGK converges to a "horizon" or neighborhood around the true solution proportional to the noise variance $\|e\|_2^2$.

Empirical Realities: Iterations vs. Wall-Clock Time

While the mathematical progress per iteration is impressive, the paper reveals a significant practical bottleneck. The computational cost of performing a dense matrix multiplication ($S^T A$) at every step is substantial.

In experiments using both synthetic models (Gaussian, Coherent, and Mixed) and real-world datasets (COVTYPE and GAS), standard block Kaczmarz consistently outperformed BGK in terms of wall-clock time. Although BGK requires fewer iterations to reach a target error, the "cost per iteration" is so high that it typically negates the algorithmic gains.

The "Smoothing" Advantage

Despite the complexity issues, BGK exhibits a unique "smoothing" property. In systems plagued by sparse, "spiky" noise, standard Kaczmarz methods often experience erratic jumps in error when they happen to sample a noisy row. Because BGK mixes all rows together via the Gaussian sketch, it effectively averages out the noise. This results in a highly stable and predictable convergence trajectory, which may be desirable in specific high-variance environments.

Pathological Success: The Mixed Model

The authors identified one specific scenario where BGK is superior: the "mixed model" matrix. In this adversarial construction, one row is random while the remaining rows are identical copies. Standard Kaczmarz methods struggle here, frequently wasting iterations on redundant information. BGK’s global mixing allows it to capture the unique information in the system immediately, leading to faster convergence in both iterations and time.

Conclusion and Future Directions

The Block Gaussian Kaczmarz method provides a robust theoretical framework for sketch-and-project methods, but its practical application is currently limited by the overhead of dense Gaussian sketching. To make this method more competitive, the authors suggest exploring:

  • Sparsified Sketches: Using sparse Gaussian or Fourier-based sketches to accelerate the matrix multiplication step.
  • Refined Bounds: Closing the gap between the theoretical requirement for large sketch collections and the empirical observation that much smaller collections suffice.
  • Inexact Systems: Applying the framework to systems where $A$ does not have full column rank.

Ultimately, BGK serves as a powerful regularizer, offering stability and theoretical elegance at the cost of raw computational speed.

Summary updated

Abstract

The Kaczmarz algorithm is one of the most popular methods for solving large-scale over-determined linear systems due to its simplicity and computational efficiency. This method can be viewed as a special instance of a more general class of sketch and project methods. Recently, a block Gaussian version was proposed that uses a block Gaussian sketch, enjoying the regularization properties of Gaussian sketching, combined with the acceleration of the block variants. Theoretical analysis was only provided for the non-block version of the Gaussian sketch method. Here, we provide theoretical guarantees for the block Gaussian Kaczmarz method, proving a number of convergence results showing convergence to the solution exponentially fast in expectation. On the flip side, with this theory and extensive experimental support, we observe that the numerical complexity of each iteration typically makes this method inferior to other iterative projection methods. We highlight only one setting in which it may be advantageous, namely when the regularizing effect is used to reduce variance in the iterates under certain noise models and convergence for some particular matrix constructions.
BibTeX
@article{needell2021block,
  author = {Deanna Needell and Elizaveta Rebrova},
  title = {{On block Gaussian sketching for the Kaczmarz method}},
  journal = {Numer. Algorithms},
  year = {2021},
  doi = {10.1007/s11075-020-00895-9},
}
Figure