Tight Convergence Bounds for the Classical Kaczmarz Method

DOI10.48550/arXiv.2609.32034MaRDI QIDQ7360698arXivFDO

Authors Jelena Diakonikolas, Runbo Yu

Publication date 25 September 2026

Published in arXiv

Tldr We provide tight convergence bounds for the classical Kaczmarz method using a fixed matrix that depends only on A and express these as relaxed bounds interpretable in terms of row norms, correlations, rank, and extremal singular values; we also explain why the cycle update converges faster than random updates when rows are weakly correlated.

Full work available at URL https://doi.org/10.48550/arXiv.2609.32034

arXiv classification

cs.DSmath.NAmath.OC

Cites work

• A randomized Kaczmarz algorithm with exponential convergence
• AIR tools II: algebraic iterative reconstruction methods, improved implementation
• Bootstrap algebraic multigrid for the 2D Wilson Dirac system
• Convergence analysis for Kaczmarz-type methods in a Hilbert space framework
• Convergence of the cyclical relaxation method for linear inequalities
• Cyclic Coordinate Dual Averaging with Extrapolation
• How catastrophic can catastrophic forgetting be in linear regression?
• Linear convergence of randomized Kaczmarz method for solving complex-valued phaseless equations
• Near-linear runtime for a classical matrix preconditioning algorithm
• Numerical Reconstruction in Magnetic Particle Imaging
• On spectral properties and fast initial convergence of the Kaczmarz method
• On the convergence rate of SOR: A worst case estimate
• Paved with good intentions: analysis of a randomized block Kaczmarz method
• Phase retrieval via randomized Kaczmarz: theoretical guarantees
• Polynomial estimates for the method of cyclic projections in Hilbert spaces
• Practical and mathematical aspects of the problem of reconstructing objects from radiographs
• Projection method for solving a singular system of linear equations and its applications
• Random reordering in SOR-type methods
• Randomized iterative methods for linear systems
• Randomized Kaczmarz converges along small singular vectors
• Randomized Kaczmarz methods with beyond-Krylov convergence
• The ASTRA Toolbox: A platform for advanced algorithm development in electron tomography
• The mathematics of computerized tomography
• The method of alternating projections and the method of subspace corrections in Hilbert space

This page was built for publication: Tight Convergence Bounds for the Classical Kaczmarz Method

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7360698)