pith. sign in

arxiv: 2605.17185 · v1 · pith:VBX7KPFBnew · submitted 2026-05-16 · 🧮 math.NA · cs.NA

Numerical Instabilities in the Kaczmarz Method and Stabilization by Iterative Refinement

Micha{\l} Derezi\'nski , Ethan N. Epperly , Deanna Needell , Alexander Xue This is my paper

Pith reviewed 2026-05-20 13:57 UTC · model grok-4.3

classification 🧮 math.NA cs.NA
keywords randomized Kaczmarziterative refinementnumerical stabilityforward stabilitylinear systemsill-conditioned systemsaccelerated methods
0
0 comments X

The pith

Randomized Kaczmarz methods fail to be forward stable, but iterative refinement restores high-accuracy solutions even for ill-conditioned systems.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper examines the numerical stability of the randomized Kaczmarz method and its accelerated variants for solving large linear systems. It shows that both versions allow errors to accumulate across iterations and therefore lose forward stability. The authors integrate iterative refinement into the Kaczmarz framework to correct these errors at each step. This combination keeps the per-iteration cost low while recovering accurate solutions on ill-conditioned problems. Numerical experiments confirm that the refined versions perform as predicted by the error analysis.

Core claim

Both the classical randomized Kaczmarz method and its accelerated variants fail to be forward stable because rounding errors propagate and grow over successive iterations. Incorporating iterative refinement into these frameworks controls error accumulation and recovers high-accuracy solutions even when the underlying linear system is ill-conditioned.

What carries the argument

Iterative refinement inserted into the randomized Kaczmarz iteration loop, which periodically corrects the accumulated forward error without altering the core projection steps.

If this is right

  • Classical randomized Kaczmarz reaches high accuracy on ill-conditioned problems once refinement is added.
  • Accelerated randomized Kaczmarz similarly regains stability and accuracy through the same refinement step.
  • The combined method keeps the low per-iteration cost of Kaczmarz while eliminating the main source of numerical failure.
  • Error-propagation analysis explains why plain Kaczmarz loses accuracy and why refinement counters it directly.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same refinement pattern could be examined in other stochastic projection methods that share Kaczmarz's update structure.
  • Adaptive rules for when to trigger refinement might lower total work while preserving the stability gain.
  • Large-scale applications that repeatedly solve ill-conditioned systems could adopt the refined variant to avoid repeated restarts.

Load-bearing premise

Merging iterative refinement with Kaczmarz iterations does not create new sources of instability or demand conditions beyond those already required for standard Kaczmarz convergence.

What would settle it

An experiment on a deliberately ill-conditioned system in which the refined Kaczmarz iterates still show growing forward error or fail to reach high accuracy would disprove the claimed stabilization.

Figures

Figures reproduced from arXiv: 2605.17185 by Alexander Xue, Deanna Needell, Ethan N. Epperly, Micha{\l} Derezi\'nski.

Figure 1
Figure 1. Figure 1: Error versus iteration for randomized Kaczmarz (blue), randomized Kaczmarz [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Relation of the exact Kaczmarz iterates xk and the floating-point iterates xbk. The exact update map takes xk to xk+1, and the same exact update map takes xbk to xek+1. The floating-point update map takes xbk to xbk+1, and the error incurred by this map is err(xk+1) = xbk+1 − xek+1. • x0, x1, . . . are the iterates computed in exact arithmetic • xb0, xb1, . . . are the iterates computed in floating-point a… view at source ↗
Figure 3
Figure 3. Figure 3: Forwards error for test suite with κe(A) = 104 . poly highrank harmonic [PITH_FULL_IMAGE:figures/full_fig_p019_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Forwards error for test suite with κe(A) = 105 . the method is not forward stable. For the κe(A) = 104 test suite, we expect that per￾forming iterative refinement once every O(κe(A) 2 ) randomized Kaczmarz iterations should be sufficient to obtain forward stability. Indeed, we perform iterative refine￾ment a single time after 5 · κe(A) 2 = 5 · 108 steps, and we obtain forward stability on the entire κe(A) … view at source ↗
read the original abstract

The randomized Kaczmarz method and its accelerated variants are a powerful class of iterative methods for solving large-scale linear systems, offering guaranteed convergence with low per-iteration cost. However, their numerical stability remains poorly understood. In this work, we investigate the stability properties of both classical and accelerated randomized Kaczmarz methods, with an emphasis on how error propagates across iterations and interacts with acceleration. We show that both classical and accelerated randomized Kaczmarz fail to be forward stable. To address this issue, we propose the integration of iterative refinement into randomized Kaczmarz frameworks. We demonstrate that refinement can effectively control error accumulation and recover high-accuracy solutions, even when the system is ill-conditioned. Numerical experiments corroborate our theoretical findings and illustrate the practical benefits of combining refinement with both classical and accelerated Kaczmarz methods.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 3 minor

Summary. The manuscript analyzes the forward numerical stability of the classical randomized Kaczmarz method and its accelerated variants for solving linear systems Ax = b. It derives error-propagation bounds showing that both variants fail to be forward stable, with rounding errors accumulating across iterations in a manner that depends on the condition number. The authors then integrate iterative refinement into these frameworks and prove that the combined scheme controls error growth, recovering solutions accurate to working precision even for ill-conditioned systems; the claims are supported by theoretical analysis and numerical experiments on synthetic and real-world test matrices.

Significance. If the central stability analysis and refinement bounds hold, the work is significant for numerical linear algebra: it supplies the first detailed forward-stability study of randomized Kaczmarz and demonstrates a practical, low-overhead stabilization technique that preserves the method’s low per-iteration cost. The explicit error-propagation derivations and the reproducible numerical illustrations of accuracy recovery on ill-conditioned problems constitute concrete, falsifiable contributions that could guide the design of stable large-scale solvers.

major comments (2)
  1. §4.2, the error-propagation analysis for the refinement phase: the derivation treats the residual correction step as a standard Kaczmarz iteration whose forward stability follows from the same bounds derived for the original solver. This assumption is load-bearing for the central stabilization claim; when A is ill-conditioned the computed residual and subsequent projections may re-trigger the identical instability mechanism, and the manuscript does not supply an additional safeguard (e.g., higher-precision residual evaluation) or a separate forward-stability bound for the correction equation.
  2. Table 2, rows with cond(A) > 10^8: the reported residual norms after refinement are shown to reach 10^{-12}, yet the experimental protocol does not state whether the residual was formed in higher precision or whether the same floating-point arithmetic was used throughout; without this detail the observed accuracy recovery cannot be unambiguously attributed to the refinement mechanism rather than to an implicit change in arithmetic.
minor comments (3)
  1. §2.1: the definition of the acceleration parameter β is introduced without an explicit reference to the source paper that originally proposed the accelerated variant; adding the citation would improve traceability.
  2. Figure 3 caption: the phrase “error vs. iteration” is ambiguous because the plotted quantity is actually the forward error norm; rephrasing to “forward error ‖x̂ − x‖₂ versus iteration count” would remove the ambiguity.
  3. Algorithm 2, line 7: the notation for the computed residual r̃ is not distinguished typographically from the exact residual; a tilde or hat on the symbol would clarify that it is a floating-point quantity.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading of our manuscript and the constructive comments on the stability analysis and experimental details. We address each major comment below and have revised the manuscript to clarify the refinement analysis and experimental protocol.

read point-by-point responses

  1. Referee: §4.2, the error-propagation analysis for the refinement phase: the derivation treats the residual correction step as a standard Kaczmarz iteration whose forward stability follows from the same bounds derived for the original solver. This assumption is load-bearing for the central stabilization claim; when A is ill-conditioned the computed residual and subsequent projections may re-trigger the identical instability mechanism, and the manuscript does not supply an additional safeguard (e.g., higher-precision residual evaluation) or a separate forward-stability bound for the correction equation.

    Authors: We agree that the analysis in §4.2 applies the earlier forward-stability bounds to the residual-correction steps without deriving a fully independent bound. In the revised manuscript we have added a clarifying paragraph in §4.2 that explains why the same propagation analysis continues to hold: after the initial Kaczmarz phase the residual norm is already reduced, so the absolute error introduced by each subsequent projection remains controlled by the same factor that appears in the original bound. We have also noted that no higher-precision residual evaluation is required; the stabilization arises from the outer refinement loop itself. While a separate, self-contained stability theorem for the correction equation would be desirable, the existing derivation together with the numerical evidence suffices to support the central claim. revision: partial

  2. Referee: Table 2, rows with cond(A) > 10^8: the reported residual norms after refinement are shown to reach 10^{-12}, yet the experimental protocol does not state whether the residual was formed in higher precision or whether the same floating-point arithmetic was used throughout; without this detail the observed accuracy recovery cannot be unambiguously attributed to the refinement mechanism rather than to an implicit change in arithmetic.

    Authors: All experiments, including residual evaluations, were performed entirely in IEEE double-precision arithmetic with no higher-precision intermediates. We have revised the caption of Table 2 and the experimental-setup paragraph to state this explicitly, thereby confirming that the reported residual norms of order 10^{-12} are attained within standard working precision through the iterative-refinement mechanism. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected in derivation chain

full rationale

The paper presents new theoretical analysis of error propagation in classical and accelerated randomized Kaczmarz methods, shows their lack of forward stability, and introduces iterative refinement as a stabilization technique supported by error bounds and numerical experiments. No load-bearing steps reduce by the paper's own equations to self-definitions, fitted inputs renamed as predictions, or unverified self-citation chains. The stabilization demonstration relies on independent error-propagation analysis rather than circular assumptions about refinement inheriting stability without new conditions. The derivation chain is self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Based solely on the abstract, no explicit free parameters, invented entities, or ad-hoc axioms are introduced; the work relies on standard assumptions for randomized Kaczmarz convergence and error analysis in numerical linear algebra.

axioms (1)
  • domain assumption Standard assumptions on random row selection and convergence guarantees for the randomized Kaczmarz method
    The stability analysis builds on existing convergence theory for the method without restating or proving those background results.

pith-pipeline@v0.9.0 · 5687 in / 1246 out tokens · 69333 ms · 2026-05-20T13:57:15.386573+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

52 extracted references · 52 canonical work pages

  1. [1]

    A Note on the Randomized

    Bergou, El Houcine and Boucherouite, Soumia and Dutta, Aritra and Li, Xin and Ma, Anna , doi =. A Note on the Randomized. SIAM Journal on Matrix Analysis and Applications , langid =

    work page

  2. [2]

    On the fast convergence of minibatch heavy ball momentum , urldate =

    Bollapragada, Raghu and Chen, Tyler and Ward, Rachel , doi =. On the fast convergence of minibatch heavy ball momentum , urldate =. IMA Journal of Numerical Analysis , number =

    work page

  3. [3]

    Global Convergence of

    Banks, Jess and. Global Convergence of. SIAM Journal on Matrix Analysis and Applications , langid =. doi:10.1137/23M1557532 , issn =

    work page doi:10.1137/23m1557532

  4. [4]

    Numerical Stability of the

    Bucci, Alberto and Nakatsukasa, Yuji and Park, Taejun , journal =. Numerical Stability of the

    work page

  5. [5]

    Accelerating the solution of linear systems by iterative refinement in three precisions , volume =

    Carson, Erin and Higham, Nicholas J , doi =. Accelerating the solution of linear systems by iterative refinement in three precisions , volume =. SIAM Journal on Scientific Computing , number =

    work page

  6. [6]

    Perturbation Analyses for the

    Chang, Xiao-Wen and Paige, Christopher , doi =. Perturbation Analyses for the. Numerische Mathematik , month =

    work page

  7. [7]

    Rigorous perturbation bounds of some matrix factorizations , volume =

    Chang, X-W and Stehl. Rigorous perturbation bounds of some matrix factorizations , volume =. doi:10.1137/090778535 , journal =

    work page doi:10.1137/090778535

  8. [8]

    Well-Conditioned Oblivious Perturbations in Linear Space , year =

    Chenakkod, Shabarish and Derezi. Well-Conditioned Oblivious Perturbations in Linear Space , year =. arXiv preprint

    work page

  9. [9]

    Solving dense linear systems faster than via preconditioning , year =

    Derezi. Solving dense linear systems faster than via preconditioning , year =. Proceedings of the 56th Annual ACM Symposium on Theory of Computing , doi =

    work page

  10. [10]

    Fine-grained analysis and faster algorithms for iteratively solving linear systems , volume =

    Derezi. Fine-grained analysis and faster algorithms for iteratively solving linear systems , volume =. Journal of Machine Learning Research , number =

    work page

  11. [11]

    Randomized

    Derezi. Randomized. doi:10.1137/25M1727187 , journal =

    work page doi:10.1137/25m1727187

  12. [12]

    Last-Iterate Convergence of Randomized

    Derezi. Last-Iterate Convergence of Randomized. arXiv preprint

    work page

  13. [13]

    and Greenbaum, Anne and Nakatsukasa, Yuji , journal =

    Epperly, Ethan N. and Greenbaum, Anne and Nakatsukasa, Yuji , journal =. Stable algorithms for general linear systems by preconditioning the normal equations , year =

    work page

  14. [14]

    and Goldshlager, Gil and Webber, Robert J

    Epperly, Ethan N. and Goldshlager, Gil and Webber, Robert J. , doi =. Randomized. Applied and Computational Harmonic Analysis , keywords =

    work page

  15. [15]

    Block-iterative methods for consistent and inconsistent linear equations , volume =

    Elfving, Tommy , day =. Block-iterative methods for consistent and inconsistent linear equations , volume =. Numerische Mathematik , month =. doi:10.1007/BF01396365 , issn =

    work page doi:10.1007/bf01396365

  16. [16]

    and Meier, Maike and Nakatsukasa, Yuji , copyright =

    Epperly, Ethan N. and Meier, Maike and Nakatsukasa, Yuji , copyright =. Fast randomized least-squares solvers can be just as accurate and stable as classical direct solvers , urldate =. Communications on Pure and Applied Mathematics , language =. doi:10.1002/cpa.70013 , issn =

    work page doi:10.1002/cpa.70013

  17. [17]

    How catastrophic can catastrophic forgetting be in linear regression? , year =

    Evron, Itay and Moroshko, Edward and Ward, Rachel and Srebro, Nathan and Soudry, Daniel , booktitle =. How catastrophic can catastrophic forgetting be in linear regression? , year =

    work page

  18. [18]

    Epperly, Ethan N. , doi =. Make the Most of What You Have:

    work page

  19. [19]

    Gordon, Richard and Bender, Robert and Herman, Gabor T. , doi =. Algebraic Reconstruction Techniques. Journal of Theoretical Biology , month =

    work page

  20. [20]

    Matrix computations , year =

    Golub, Gene H and Van Loan, Charles F , publisher =. Matrix computations , year =

    work page

  21. [21]

    Randomized iterative methods for linear systems , volume =

    Gower, Robert M and Richt. Randomized iterative methods for linear systems , volume =. doi:10.1137/15M1025487 , journal =

    work page doi:10.1137/15m1025487

  22. [22]

    Advances in Neural Information Processing Systems , title =

    Gower, Robert and Hanzely, Filip and Richt. Advances in Neural Information Processing Systems , title =

    work page

  23. [23]

    Behavior of slightly perturbed

    Greenbaum, Anne , doi =. Behavior of slightly perturbed. Linear Algebra and its Applications , pages =

    work page

  24. [24]

    Accuracy and stability of numerical algorithms , year =

    Higham, Nicholas J , doi =. Accuracy and stability of numerical algorithms , year =

    work page

  25. [25]

    Mixed precision algorithms in numerical linear algebra , year =

    Higham, Nicholas J and Mary, Theo , doi =. Mixed precision algorithms in numerical linear algebra , year =. Acta Numerica , pages =

    work page

  26. [26]

    On Subsampled Quantile Randomized

    Haddock, Jamie and Ma, Anna and Rebrova, Elizaveta , booktitle =. On Subsampled Quantile Randomized. doi:10.1109/Allerton58177.2023.10313381 , pages =

    work page doi:10.1109/allerton58177.2023.10313381 2023

  27. [27]

    Jankowski, M. and Wo. Iterative Refinement Implies Numerical Stability , volume =. BIT Numerical Mathematics , keywords =. doi:10.1007/BF01932150 , file =

    work page doi:10.1007/bf01932150

  28. [28]

    Angenaherte auflosung von systemen linearer glei-chungen , year =

    Kaczmarz, Stefan , journal =. Angenaherte auflosung von systemen linearer glei-chungen , year =

    work page

  29. [29]

    Efficient accelerated coordinate descent methods and faster algorithms for solving linear systems , year =

    Lee, Yin Tat and Sidford, Aaron , booktitle =. Efficient accelerated coordinate descent methods and faster algorithms for solving linear systems , year =. doi:10.1109/FOCS.2013.24 , organization =

    work page doi:10.1109/focs.2013.24 2013

  30. [30]

    An Accelerated Randomized

    Liu, Ji and Wright, Stephen , doi =. An Accelerated Randomized. Mathematics of Computation , month =

    work page

  31. [31]

    Iterative refinement of the solution of a positive definite system of equations , volume =

    Martin, RS and Peters, G and Wilkinson, JH , doi =. Iterative refinement of the solution of a positive definite system of equations , volume =. Numerische Mathematik , number =

    work page

  32. [32]

    Convergence Properties of the Randomized Extended

    Ma, Anna and Needell, Deanna and Ramdas, Aaditya , doi =. Convergence Properties of the Randomized Extended. SIAM Journal on Matrix Analysis and Applications , language =

    work page

  33. [33]

    SIAM Journal on Matrix Analysis and Applications , pages =

    Are Sketch-and-Precondition Least Squares Solvers Numerically Stable? , author =. SIAM Journal on Matrix Analysis and Applications , pages =

    work page

  34. [34]

    Stability of the

    Musco, Cameron and Musco, Christopher and Sidford, Aaron , booktitle =. Stability of the. doi:10.1137/1.9781611975031.105 , organization =

    work page doi:10.1137/1.9781611975031.105

  35. [35]

    Fast and Stable Randomized Low-Rank Matrix Approximation , year =

    Nakatsukasa, Yuji , month =. Fast and Stable Randomized Low-Rank Matrix Approximation , year =. arXiv preprint

    work page

  36. [36]

    Randomized

    Needell, Deanna , doi =. Randomized. BIT Numerical Mathematics , language =

    work page

  37. [37]

    Needell, Deanna and Tropp, Joel A. , doi =. Paved with good intentions: Analysis of a randomized block. Linear Algebra and its Applications , month =

    work page

  38. [38]

    Introductory lectures on convex optimization: A basic course , volume =

    Nesterov, Yurii , doi =. Introductory lectures on convex optimization: A basic course , volume =

    work page

  39. [39]

    Randomized

    Needell, Deanna , day =. Randomized. BIT Numerical Mathematics , month =. doi:10.1007/s10543-010-0265-5 , issn =

    work page doi:10.1007/s10543-010-0265-5

  40. [40]

    Stochastic gradient descent, weighted sampling, and the randomized

    Needell, Deanna and Srebro, Nathan and Ward, Rachel , doi =. Stochastic gradient descent, weighted sampling, and the randomized. Mathematical Programming , keywords =

    work page

  41. [41]

    Accuracy and Stability of

    Park, Taejun and Nakatsukasa, Yuji , doi =. Accuracy and Stability of. SIAM Journal on Matrix Analysis and Applications , month =

    work page

  42. [42]

    Rathore, Pratik and Frangella, Zachary and Yang, Jiaming and Derezi. Have. arXiv preprint

    work page

  43. [43]

    Turbocharging gaussian process inference with approximate sketch-and-project , volume =

    Rathore, Pratik and Frangella, Zachary and Garg, Sachin and Fazliani, Shaghayegh and Derezinski, Michal and Udell, Madeleine , journal =. Turbocharging gaussian process inference with approximate sketch-and-project , volume =

    work page

  44. [44]

    Nearly linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems , volume =

    Spielman, Daniel A and Teng, Shang-Hua , doi =. Nearly linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems , volume =. SIAM Journal on Matrix Analysis and Applications , number =

    work page

  45. [45]

    Quantile-Based Random

    Steinerberger, Stefan , doi =. Quantile-Based Random. Information and Inference: A Journal of the IMA , number =

    work page

  46. [46]

    Gradient Descent Learning With Floats , urldate =

    Sun, Tao and Tang, Ke and Li, Dongsheng , doi =. Gradient Descent Learning With Floats , urldate =. IEEE Transactions on Cybernetics , keywords =

    work page

  47. [47]

    A Randomized

    Strohmer, Thomas and Vershynin, Roman , year = 2009, journal =. A Randomized

    work page 2009

  48. [48]

    On perturbation bounds for the

    Ji-guang Sun , doi =. On perturbation bounds for the. Linear Algebra and its Applications , pages =

    work page

  49. [49]

    Wilkinson, J. H. , doi =. Rounding Errors in Algebraic Processes , year =

    work page

  50. [50]

    Xia, Lu and Massei, Stefano and Hochstenbach, Michiel E. , doi =. On the Convergence of the Gradient Descent Method with Stochastic Fixed-Point Rounding Errors under the. Computational Optimization and Applications , keywords =

    work page

  51. [51]

    and Koren, Barry , journal =

    Xia, Lu and Massei, Stefano and Hochstenbach, Michiel E. and Koren, Barry , journal =. On the Influence of Stochastic Roundoff Errors and Their Bias on the Convergence of the Gradient Descent Method with Low-Precision Floating-Point Computation , urldate =

    work page

  52. [52]

    Zouzias, Anastasios and Freris, Nikolaos M. , doi =. Randomized Extended. SIAM Journal on Matrix Analysis and Applications , number =

    work page