# Faster randomized block Kaczmarz algorithms

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Feb 2019.

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

- [Randomized Kaczmarz with geometrically smoothed momentum](https://mlsanity.com/paper/2401.09415/) (2024)
- [An optimal scheduled learning rate for a randomized Kaczmarz algorithm](https://mlsanity.com/paper/2202.12224/) (2022)
- [A Note on Randomized Kaczmarz Algorithm for Solving Doubly-Noisy Linear Systems](https://mlsanity.com/paper/2308.16904/) (2023)
- [Power of ℓ1-Norm Regularized Kaczmarz Algorithms for High-Order Tensor Recovery](https://mlsanity.com/paper/2405.08275/) (2024)
- [Randomized batch-sampling Kaczmarz methods for solving linear systems](https://mlsanity.com/paper/2511.09872/) (2025)

## Abstract (arXiv)

The Kaczmarz algorithm is a simple iterative scheme for solving consistent linear systems. At each step, the method projects the current iterate onto the solution space of a single constraint. Hence, it requires very low cost per iteration and storage, and it has a linear rate of convergence. Distributed implementations of Kaczmarz have become, in recent years, the de facto architectural choice for large-scale linear systems. Therefore, in this paper we develop a family of randomized block Kaczmarz algorithms that uses at each step a subset of the constraints and extrapolated stepsizes, and can be deployed on distributed computing units. Our approach is based on several new ideas and tools, including stochastic selection rule for the blocks of rows, stochastic conditioning of the linear system, and novel strategies for designing extrapolated stepsizes. We prove that randomized block Kaczmarz algorithm converges linearly in expectation, with a rate depending on the geometric properties of the matrix and its submatrices and on the size of the blocks. Our convergence analysis reveals that the algorithm is most effective when it is given a good sampling of the rows into well-conditioned blocks. Besides providing a general framework for the design and analysis of randomized block Kaczmarz methods, our results resolve an open problem in the literature related to the theoretical understanding of observed practical efficiency of extrapolated block Kaczmarz methods.