Pith. sign in

REVIEW 3 major objections 4 minor 25 references

The paper claims that regularizing block solves and weighing blocks by orthogonality plus residual yields a block-Kaczmarz rate controlled by the block's smallest nonzero singular value, with speedups up to 59x over TA-ReBlocK-U.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review

2026-08-04 12:42 UTC pith:CGPXHFUC

load-bearing objection A clever block-Kaczmarz variant with real empirical speedups, but the main convergence theorem has a genuine gap and the ill-conditioned experiments overstate accuracy. the 3 major comments →

arxiv 2510.02156 v2 pith:CGPXHFUC submitted 2025-10-02 math.NA cs.NA

A fast solver for ill-conditioned linear systems using randomized stable solutions of its blocks

Suvendu Kar , Murugesan Venkatapathi This is my paper
classification math.NA cs.NA MSC 15A0665F0865F1065F2565F55
keywords randomized block-Kaczmarzill-conditioned linear systemsregularizationorthogonal blocksresidual-based samplingflexible GMRESleast-squaresconvergence analysis
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

This paper introduces ROR-BK, a randomized block-Kaczmarz iteration for solving consistent linear systems that is specifically designed for ill-conditioned matrices. The key idea is to replace the exact block pseudo-inverse with a regularized version, BT(BBT + λI)^{-1}, and to sample blocks with probability that reflects each block's effective orthogonality to all others, while also adding a dynamic block made of rows with the largest current residuals. The central theoretical claim is Theorem 2.3: each update contracts the error in expectation by λ/(λ + λ_min^+), where λ_min^+ is the smallest nonzero eigenvalue of the chosen block's Gram matrix. Empirically, on sparse and dense ill-conditioned square, over-determined and under-determined systems, ROR-BK needs 2.5-15x fewer iterations than SOBK and TA-ReBlocK-U, with 1.4-4.5x CPU speedups over SOBK and up to 59x over TA-ReBlocK-U. If correct, the method offers a preconditioner-free alternative that can also be embedded as an inner iteration in flexible GMRES.

Core claim

The paper's central claim is that the regularized block projection M = A_τ^T(A_τ A_τ^T + λI)^{-1} A_τ — which Lemma 2.1 rewrites as I - λ(A_τ^T A_τ + λI)^{-1} — makes each randomized block update contract the error by the factor λ/(λ_min^+ + λ), where λ_min^+ is the smallest nonzero eigenvalue of the sampled block's Gram matrix (Theorem 2.3). The algorithm then feeds this stabilized operator with two stochastic selection rules: a fixed distribution weighted by each block's effective orthogonality to all other blocks (computed from block centroids), and a dynamic block composed of the rows with the largest current residual components. On top of the algorithmic description, the paper claims th

What carries the argument

The machinery is the pair (regularized block inverse, sampling weights). The regularized inverse operator M_τ = A_τ^T(A_τ A_τ^T + λI)^{-1}A_τ acts as a stable relaxed projection; the Woodbury identity (Lemma 2.1) turns it into I - λ(A_τ^T A_τ + λI)^{-1}, which exposes the contraction factor λ/(λ_min^+ + λ). The sampling is driven by the centroid cosine matrix C, from which the orthogonality distribution P is built (P_t ∝ exp(-k Σ_m C_{t,m}^2)), and by a residual-sorted dynamic block of top ⌊m/k⌋ rows. The choice of which block acts at each update determines which λ_min^+ enters the contraction bound.

Load-bearing premise

The per-step contraction factor is derived under the assumption that the error vector at every iteration lies in the range space of the transpose of the block just selected; if the error has a component in that block's null space, that component is untouched and the stated rate does not follow.

What would settle it

Use a 2-block consistent system with blocks A_1 = [0 1] and A_2 = [1 0], b = 0, so x* = 0. Start x_0 = (1,0)^T and force the sampler to choose block 1 in a single iteration; the update leaves x_1 = x_0, so the error norm does not decrease by the claimed factor λ/(1+λ), contradicting Theorem 2.3's per-update bound.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

Share X Bluesky LinkedIn Reddit HN

If this is right

  • If Theorem 2.3 is correct, the expected error of ROR-BK decreases linearly at the rate λ/(λ_min^+ + λ), independent of the global condition number of A, so ill-conditioned systems can be advanced reliably without a preconditioner.
  • The method's measured iteration reductions (2.5-15x over SOBK and TA-ReBlocK-U) translate directly into CPU time savings, making it a plausible default for large sparse ill-conditioned systems where incomplete-factorization preconditioners are fragile.
  • Because ROR-BK is row-block based and works for under-, square, and over-determined systems, it can serve as an inner iteration in flexible GMRES (Algorithm 2.2), extending the reach of inner-iteration preconditioning to least-squares problems.
  • The residue-based dynamic block combined with regularization suggests that a stable solver can target the largest residual rows without paying a conditioning penalty, which is the paper's stated reason for the gains on highly over/under-determined dense systems.

Where Pith is reading between the lines

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

  • A proof-level strengthening that would fully establish Theorem 2.3 is to show the error vector's component orthogonal to the selected block's row space is either bounded or handled by the other updates; until then, the rate is guaranteed only for iterates whose error lies in the block's co-range. A natural attempt: replace the range assumption with a projected-error bound and add a correction term
  • The orthogonality-weighted sampling built from block centroids is cheap (O(mn + k^2 n)) and could be reused in other row-subset iterative methods, e.g., randomized coordinate descent for least squares.
  • A testable extension is to choose λ adaptively per block using estimates of λ_min^+; the theory suggests an optimal trade-off between fast contraction (small λ) and numerical stability (large λ) that the paper's fixed 1e-6·block-size choice does not explore.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper proposes ROR-BK, a randomized block-Kaczmarz method that combines three ingredients: regularized block solves, sampling of blocks according to a centroid-based orthogonality measure, and a residual-based dynamic block aggregation. It claims a per-step contraction bound and expected linear convergence (Theorem 2.3), and it reports CPU and iteration speedups against SOBK and TA-ReBlocK-U on sparse and dense, square and rectangular, well- and ill-conditioned systems. The paper also proposes a flexible GMRES variant using ROR-BK as an inner preconditioner. The central theoretical result, however, is not valid as stated, and the numerical reporting of relative solution errors needs clarification.

Significance. If the convergence guarantee were correct, the paper would offer a simple and practically effective extension of the block-Kaczmarz framework, with the attractive property of avoiding explicit preconditioning. The numerical study is broad and the reported speedups (1.4x–4.5x over SOBK and up to 59x over TA-ReBlocK-U) are substantial. The algorithm is clearly specified, and the cost discussion for the block solves is useful. However, the main theorem is invalid for rank-deficient blocks, which are exactly the underdetermined regimes the paper targets. The empirical section also reports relative errors near 0.8 without explaining that, for underdetermined systems, the iterates converge to the minimum-norm solution and not to a randomly generated reference solution. The paper is therefore not acceptable in its present form, although the underlying algorithmic idea may be salvageable with a corrected analysis.

major comments (3)
  1. [Theorem 2.3, Eq. (2.13)] The per-step contraction bound is false when the selected block Aτ is rank-deficient. The proof bounds ||λ(AτᵀAτ + λI)⁻¹(xt − x*)|| using the smallest nonzero eigenvalue of AτᵀAτ, but this is valid only when xt − x* lies in R(Aτᵀ). Lemma 2.2 guarantees only xt − x* ∈ R(Aᵀ), which is generally larger than R(Aτᵀ). For any nonzero v ∈ N(Aτ), λ(AτᵀAτ + λI)⁻¹v = v, so the null-space component is left unchanged. Hence Eq. (2.13) should have contraction factor 1 on those components, and the expected linear rate in Eq. (2.14) is unsupported. This affects exactly the underdetermined and rank-deficient block cases that the method is designed to handle. Either the theorem must be restricted to full-column-rank blocks, or the analysis must track convergence in R(Aτᵀ) and handle null-space components separately.
  2. [Section 3.2, Tables 2 and 3] The reported relative errors are inconsistent with the claim that the method is 'solving' ill-conditioned systems. In Table 2, all methods report RE ≈ 0.38–0.79, and in Table 3 the underdetermined randn(20000×60000) case reports RE ≈ 0.816 for all methods despite RRN < 1e-6. For underdetermined consistent systems, the ROR-BK iterates with x0=0 converge to the minimum-norm solution A⁺b, not to an arbitrary random x* satisfying Ax*=b. Comparing RE against a random x* is therefore not meaningful. The phrase 'RE indicates indeed that the solutions are converging' is misleading; a residual-norm reduction does not imply the relative solution error is small. The experiments should compare against A⁺b for underdetermined problems, or clearly state that only residual convergence is being measured.
  3. [Theorem 2.4, Eq. (2.16)] The claim that selecting the rows with largest residual entries 'minimizes the upper and lower bounds of the error' is not established. The bounds in Eq. (2.16) depend on λ_min⁺(AτᵀAτ) and λ_max⁺(AτᵀAτ) of the selected block, and these quantities are not uniformly bounded over all possible subsets of rows of A. The sentence 'λ_min⁺, λ_max⁺ are bounded for a given system' is not justified for arbitrary block selections. This weakens Theorem 2.4, which is one of the paper's justifications for the residual-based aggregation step.
minor comments (4)
  1. [Lemma 2.1] The Woodbury identity proof is algebraically incorrect: the displayed expression with 1/λ³ M(MᵀM + λI)Mᵀ is not the inverse of (λI + MMᵀ). The lemma's statement is true, but the proof should be corrected, for example by direct multiplication or by using the standard Woodbury formula with the correct prefactor 1/λ.
  2. [Section 3.1] The notation is inconsistent: in Algorithm 2.1, k denotes the number of blocks, but in Section 3.1 the text says 'the number of rows in a block k=100'. Please use a different symbol, e.g. bsize, for the block row count.
  3. [Throughout] There are several typos and formatting issues: 'Woodberry' should be 'Woodbury', 'Moor-Penrose' should be 'Moore-Penrose', 'F ranz10' should be 'Franz10', and 'residue/residual' are used interchangeably. The table captions also contain broken LaTeX-like artifacts such as 'X m k'.
  4. [Appendix, Theorem 5.2] The proof of Theorem 5.2 is deferred to Theorem 4.1 of [7] with only a one-sentence explanation. If this result is included as a theorem, a self-contained proof or a precise statement of the invoked result and hypotheses should be provided.

Circularity Check

0 steps flagged

No circular derivation: ROR-BK's analysis is self-contained, and the only self-citation is motivational rather than load-bearing.

full rationale

The paper's derivation chain does not reduce any predicted or derived quantity to its own inputs. Theorem 2.3 derives a contraction factor from the regularized block update rule via the matrix identity in Lemma 2.1; even if the proof has a subspace gap (the error vector is only shown to lie in R(A^T), while the spectral bound used in (2.13) would require R(A_tau^T)), that is a correctness/bound issue, not circularity. Lemma 2.2 is an induction on the update formula, and Theorem 2.4 is an algebraic bound; neither defines its conclusion in terms of the quantity it claims to predict. The residue-based block selection in Algorithm 2.1 chooses rows maximizing the residual term that appears in the Theorem 2.4 bound (2.16); this is a selection/optimality argument, not a fitted parameter renamed as a prediction. Theorem 5.2 explicitly relies on Theorem 4.1 of [7], an external prior work by Goldshlager, Hu, and Lin, and the appendix proof is cited rather than re-derived; this is legitimate external support, not self-citation. The only self-citation is reference [11] (Jain, Manglani, and Venkatapathi), used in the introduction to support the general observation that preconditioners may not improve backward conditioning; it is motivational and does not bear the weight of the convergence theorems. Numerical comparisons are run against external baselines SOBK and TA-ReBlocK-U, so the empirical claims are not self-referential. The skeptical concern about Theorem 2.3 is a potential mathematical gap, but it does not make the argument circular. Accordingly, no circularity step is found.

Axiom & Free-Parameter Ledger

4 free parameters · 3 axioms · 0 invented entities

The paper introduces no new physical or mathematical entities. Its load-bearing axioms are standard linear algebra plus an implicit, unproven subspace assumption in the convergence proof. The free parameters (regularization, block count, sampling exponents) are chosen by the authors without sensitivity analysis.

free parameters (4)
  • regularization parameter tilde_lambda = 1e-6 * (rows per block) in experiments
    Regularization strength in block updates; chosen a priori per problem size, not derived; affects convergence speed and stability.
  • number of blocks k = 100 in experiments
    Determines block size and the residual-block size; sensitivity not analyzed.
  • orthogonality update count l = 3
    Number of orthogonality-based updates per iteration; chosen by user, no theoretical justification.
  • exponent factor in proposal distribution = k (block count) inside exp(-k * sum C^2)
    The scaling of the orthogonality weighting is ad hoc and not derived; it controls the sampling distribution and is not validated.
axioms (3)
  • standard math Standard linear algebra identities (Woodbury, pseudoinverse properties)
    Used in Lemma 2.1 and throughout; assumed from textbooks.
  • domain assumption The system Ax=b is consistent and x* is the minimum-norm solution
    Theorem 2.3 and Remark 2.5 rely on x* = A^+ b; least-squares extensions are relegated to the appendix.
  • ad hoc to paper The error vector lies in the range of the selected block's transpose, R(A_tau^T), enabling the eigenvalue bound in Theorem 2.3
    This is an unstated assumption on which the contraction proof depends; Lemma 2.2 only proves R(A^T), not R(A_tau^T). Counterexamples show the bound is false without it.

reviewed 2026-08-04 · how reviews work

0 comments
Cite this review

Pith. "Pith review of A fast solver for ill-conditioned linear systems using randomized stable solutions of its blocks." pith.science (2026). https://pith.science/paper/CGPXHFUC

@misc{pith2026251002156,
  author       = {Pith},
  title        = {Pith review of: A fast solver for ill-conditioned linear systems using randomized stable solutions of its blocks},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CGPXHFUC}},
  note         = {Machine review of arXiv:2510.02156}
}
Share X Bluesky LinkedIn Reddit HN
read the original abstract

We present an enhanced version of the row-based randomized block-Kaczmarz method to solve a linear system of equations. This improvement makes use of a regularization during block updates in the solution, and a dynamic proposal distribution based on the current residual vector and effective mutual orthogonality between all blocks. The improved method provides significant gains in solving highly ill-conditioned linear systems that are either sparse, or dense least-squares problems that are significantly over/under determined. Considering the poor guarantees in effectively preconditioning iterative solutions for such ill-conditioned problems, it may also serve as a pre-solver for accelerating other iterative numerical methods, and as an inner iteration in certain types of GMRES solvers for linear systems.

Figures

Figures reproduced from arXiv: 2510.02156 by Murugesan Venkatapathi, Suvendu Kar.

Figure 1
Figure 1. Figure 1: Representation of solution updates in block-Kaczmarz methods. [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗

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

25 extracted references · 9 canonical work pages

  1. [1]

    Bai and W.-T

    Z.-Z. Bai and W.-T. Wu, On greedy randomized kaczmarz method for solving large sparse linear systems, SIAM Journal on Scientific Computing, 40 (2018), pp. A592–A606, https: //doi.org/10.1137/17M1137747

    doi:10.1137/17m1137747 2018

  2. [2]

    Bai and W.-T

    Z.-Z. Bai and W.-T. Wu, On relaxed greedy randomized kaczmarz methods for solving large sparse linear systems, Applied Mathematics Letters, 83 (2018), pp. 21–26, https://doi.org/ 10.1016/j.aml.2018.03.008

    work page doi:10.1016/j.aml.2018.03.008 2018

  3. [3]

    Bai and W.-T

    Z.-Z. Bai and W.-T. Wu, On greedy randomized augmented kaczmarz method for solving large sparse inconsistent linear systems, SIAM Journal on Scientific Computing, 43 (2021), pp. A3892–A3911, https://doi.org/10.1137/20M1352235

    work page doi:10.1137/20m1352235 2021

  4. [4]

    Chan and A

    W. Chan and A. George, A linear time implementation of the reverse cuthill-mckee algo- rithm, BIT, 20 (1980), p. 8 – 14, https://doi.org/10.1007/BF01933580

    work page doi:10.1007/bf01933580 1980

  5. [5]

    T. A. Davis and Y. Hu, The university of florida sparse matrix collection , ACM Trans. Math. Softw., 38 (2011), https://doi.org/10.1145/2049662.2049663

    arXiv 2011

  6. [6]

    Y.-S. Du, K. Hayami, N. Zheng, K. Morikuni, and J.-F. Yin, Kaczmarz-type inner-iteration preconditioned flexible gmres methods for consistent linear systems , SIAM Journal on Sci- entific Computing, 43 (2021), pp. S345–S366, https://doi.org/10.1137/20M1344937

    work page doi:10.1137/20m1344937 2021

  7. [7]

    Goldshlager, J

    G. Goldshlager, J. Hu, and L. Lin, Worth their weight: Randomized and regularized block kaczmarz algorithms without preprocessing , 2025, https://arxiv.org/abs/2502.00882

    arXiv 2025

  8. [8]

    Gordon, R

    R. Gordon, R. Bender, and G. T. Herman, Algebraic reconstruction techniques (art) for three-dimensional electron microscopy and x-ray photography, Journal of Theoretical Biol- ogy, 29 (1970), pp. 471–481, https://doi.org/10.1016/0022-5193(70)90109-8

    doi:10.1016/0022-5193(70)90109-8 1970

  9. [9]

    D. A. Harville, Matrix algebra from a statistician ’s perspective , 1998, https://doi.org/10. 1080/00401706.1998.10485214

    arXiv 1998

  10. [10]

    Hayami, J.-F

    K. Hayami, J.-F. Yin, and T. Ito, Gmres methods for least squares problems , SIAM Journal on Matrix Analysis and Applications, 31 (2010), pp. 2400–2430, https://doi.org/10.1137/ 070696313

    2010

  11. [11]

    P. Jain, K. Manglani, and M. Venkatapathi, Error estimators and their analysis for cg, bi-cg, and gmres , Numerical Analysis and Applications, 16 (2023), pp. 135–153, https: //doi.org/10.1134/S1995423923020040

    work page doi:10.1134/s1995423923020040 2023

  12. [12]

    Jiang, K

    X.-L. Jiang, K. Zhang, and J.-F. Yin, Randomized block kaczmarz methods with k-means clustering for solving large linear systems , Journal of Computational and Applied Mathe- matics, 403 (2022), p. 113828, https://doi.org/10.1016/j.cam.2021.113828

    arXiv 2022

  13. [13]

    Karczmarz, Angenaherte auflosung von systemen linearer glei-chungen , Bull

    S. Karczmarz, Angenaherte auflosung von systemen linearer glei-chungen , Bull. Int. Acad. Pol. Sic. Let., Cl. Sci. Math. Nat., (1937), pp. 355–357, http://refhub.elsevier.com/ S0893-9659(25)00079-5/sb1

    1937

  14. [14]

    Kushida, Condition number estimation of preconditioned matrices , PLoS One, 10 (2015), p

    N. Kushida, Condition number estimation of preconditioned matrices , PLoS One, 10 (2015), p. e0122331, https://doi.org/10.1371/journal.pone.0122331. Erratum in: PLoS One. 2015 Jun 17;10(6):e0130920. doi: 10.1371/journal.pone.0130920

    work page doi:10.1371/journal.pone.0122331 2015

  15. [15]

    Liang and H.-B

    Y.-F. Liang and H.-B. Li, Orthogonal block kaczmarz algorithm based on preprocessing tech- nology, 2024, https://arxiv.org/abs/2401.00672v3

    Pith/arXiv arXiv 2024

  16. [16]

    Miao and W.-T

    C.-Q. Miao and W.-T. Wu, On greedy randomized average block kaczmarz method for solving large linear systems , Journal of Computational and Applied Mathematics, 413 (2022), p. 114372, https://doi.org/10.1016/j.cam.2022.114372

    arXiv 2022

  17. [17]

    Morikuni and K

    K. Morikuni and K. Hayami, Convergence of inner-iteration gmres methods for rank-deficient least squares problems , SIAM Journal on Matrix Analysis and Applications, 36 (2015), pp. 225–250, https://doi.org/10.1137/130946009

    work page doi:10.1137/130946009 2015

  18. [18]

    Niu and B

    Y.-Q. Niu and B. Zheng, A greedy block kaczmarz algorithm for solving large-scale linear systems, Applied Mathematics Letters, 104 (2020), p. 106294, https://doi.org/10.1016/j. aml.2020.106294

    arXiv 2020

  19. [19]

    Saad, Preconditioning techniques for nonsymmetric and indefinite linear systems , Journal of Computational and Applied Mathematics, 24 (1988), pp

    Y. Saad, Preconditioning techniques for nonsymmetric and indefinite linear systems , Journal of Computational and Applied Mathematics, 24 (1988), pp. 89–105, https://doi.org/https: //doi.org/10.1016/0377-0427(88)90345-7

    work page doi:10.1016/0377-0427(88)90345-7 1988

  20. [20]

    Strohmer and R

    T. Strohmer and R. Vershynin, A randomized kaczmarz algorithm with exponential conver- gence, Journal of Fourier Analysis and Applications, 15 (2009), pp. 262–278

    2009

  21. [21]

    Wu, On two-subspace randomized extended kaczmarz method for solving large linear least-squares problems , Numerical Algorithms, 89 (2022), pp

    W.-T. Wu, On two-subspace randomized extended kaczmarz method for solving large linear least-squares problems , Numerical Algorithms, 89 (2022), pp. 1–31, https://doi.org/10. 1007/s11075-021-01104-x

    2022

  22. [22]

    J. Z. Xia Xin, Effective and robust preconditioning of general spd matrices via structured incomplete factorization , SIAM J. Matrix Anal. Appl., 38 (2017), p. 1298–1322, https: //doi.org/10.1137/17M1124152, https://doi.org/10.1137/17M1124152

    work page doi:10.1137/17m1124152 2017

  23. [23]

    Ye, Preconditioning for accurate solutions of ill-conditioned linear systems , Numerical Lin- ear Algebra with Applications, 27 (2020), p

    Q. Ye, Preconditioning for accurate solutions of ill-conditioned linear systems , Numerical Lin- ear Algebra with Applications, 27 (2020), p. e2315, https://doi.org/https://doi.org/10. 14 SUVENDU KAR AND MURUGESAN VENKATAPATHI 1002/nla.2315

    2020

  24. [24]

    Zhang, M.-L

    X.-F. Zhang, M.-L. Xiao, and Z.-H. He, Orthogonal block kaczmarz inner-iteration precondi- tioned flexible gmres method for large-scale linear systems , Applied Mathematics Letters, 166 (2025), p. 109529, https://doi.org/10.1016/j.aml.2025.109529

    arXiv 2025

  25. [25]

    Appendix. 5.1. Initial Solutions. Let us now provide an procedure to find an initial solu- tion x0P RpATq, such that }b´Ax0} }b} ď 1. Algorithm 5.1 Initial Solution Require: A, b Ensure: x0 1: Compute yÐ sum of a set of rows in A. 2: ˜bÐ Ay 3: x0Ð xb,˜by }˜b}2 2 y 4: Return x0 Remark 5.1. The initial solution x0 from Algorithm 5.1 is in RpATq, and }b´Ax0}...

This paper was first reviewed by deepseek-v4-flash on August 4, 2026.