Pith. sign in

REVIEW 3 major objections 3 minor 1 cited by

Connecting randomized iterative methods with Krylov subspaces

T0 review · 3 major / 3 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read A single projection rule, tuned by a memory length, unifies randomized Kaczmarz and Krylov subspace solvers into one family.

desk verdict A genuinely useful unified affine-subspace framework that interpolates between randomized iterative methods and CGNE, but only for consistent systems; the bridge to inconsistent least squares is not proven and the claims should be qualified. read the letter →

arxiv 2505.20602 v1 pith:DGRSSBNZ submitted 2025-05-27 math.NA cs.NA

Yonghan Sun , Deren Han , Jiaxin Xie This is my paper · ORCID
classification math.NAcs.NA MSC 65F1065F2090C2515A0668W20
keywords stochasticmethodsKrylovsubspaceKaczmarzmethoditerativesketchinglinearsystemslimitedmemory
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper argues that two families of linear-system solvers that have been studied separately---randomized iterative methods such as randomized Kaczmarz, and deterministic Krylov subspace methods such as CGNE---are the two endpoints of one spectrum. The proposed iteration projects the (unknown) solution $A^\dagger b$ onto the affine subspace spanned by the last $\ell$ iterates together with one newly sketched normal direction. With $\ell=1$ the projection recovers randomized iterative methods; with $\ell=\infty$ and no sketching it recovers the conjugate gradient normal equation method; intermediate $\ell$ yields the new IS-Krylov family. The paper proves linear convergence in expectation with contraction factor $1-q_k\sigma_{\min}^2(H^{1/2}A)$, shows that larger $\ell$ improves this bound, and proves finite termination in $\mathrm{rank}(A)$ steps when $\ell\ge \mathrm{rank}(A)$. If correct, this gives a parameterized family of solvers that interpolates between low-cost randomized iterations and memory-intensive deterministic Krylov methods.

What carries the argument

The central object is the affine subspace $\Pi_k$ and the projection of $A^\dagger b$ onto it. Two additional mechanisms make the projection practical and bridge to Krylov theory: the identity (7), which shows previous iterates are orthogonal to the error so that the normal equations collapse to $M_k^\top M_k s_k=\gamma_k e_{k-j_k+1}$; and the closed-form inverse of $V_k^\top V_k$ given by the matrix $C(\alpha_1,\ldots,\alpha_n)$ of Lemma 3.7, which reduces the per-iteration cost to $O(n(k-j_k+1))$. Algorithm 3 rewrites the same update as a Gram-Schmidt orthogonalization of the sketched normal direction $d_k$ against the previous search directions $p_i$; this form is what identifies the $\ell=\infty$, no-sketch limit with the Lanczos/CGNE iteration.

What would settle it

In exact arithmetic, take a consistent system with $\mathrm{rank}(A)=r$, set $\ell=r$, and run Algorithm 3; Remark 3.6 predicts $x_r = A^\dagger b$ exactly. A concrete test: $A=\mathrm{diag}(1,1/2,1/3)$, $b=Ax_*$, $x_0=0$, $\ell=3$ --- the third iterate should equal $x_*$; any run where $x_3\neq x_*$ (barring round-off) falsifies the finite-termination claim. Alternatively, average the squared error over many independent sketching trials and compare the empirical contraction factor with the bound $1-q_k\sigma_{\min}^2(H^{1/2}A)$; a systematic violation of the bound would falsify Theorem 3.3.

Watch

Extended reading notes

Core claim

The paper's central claim is that iteration (2), the orthogonal projection of $A^\dagger b$ onto $\Pi_k=\mathrm{aff}\{x_{j_k},\ldots,x_k, x_k - A^\top S_k S_k^\top(Ax_k-b)\}$, is a common generalization. The key algebraic mechanism is that the projection can be computed without knowing $A^\dagger b$: the orthogonality of past iterates collapses the normal equations to $M_k^\top M_k s_k = \gamma_k e_{k-j_k+1}$ with $\gamma_k=\|S_k^\top(Ax_k-b)\|^2$. From this, the paper recovers: $\ell=1$ gives the randomized iterative framework with stochastic Polyak stepsizes, including randomized Kaczmarz (Remark 3.2); $\ell=2$ gives the adaptive stochastic heavy-ball / stochastic conjugate gradient scheme; and $\ell=\infty$ with $\Omega=\{I\}$ gives exactly CGNE, with the search directions forming an orthogonal basis of the Krylov subspace $\mathcal{K}_{k+1}(A^\top A, A^\top r_0)$ (Section 4.3). The convergence theorem states $\mathbb{E}_{S_k}[\|x_{k+1}-A^\dagger b\|_2^2 \mid x_k]\le (1-q_k\sigma_{\min}^2(H^{1/2}A))\|x_k-A^\dagger b\|_2^2$ with $H=\mathbb{E}[SS^\top/\|S^\top A\|_2^2]$, and Remark 3.6 proves exact finite termination in $\mathrm{rank}(A)$ steps when $\ell\ge \mathrm{rank}(A)$.

Load-bearing premise

The convergence analysis assumes the linear system $Ax=b$ is consistent; the key identity $\langle A^\top S S^\top(Ax-b), x-A^\dagger b\rangle = \|S^\top(Ax-b)\|^2$ holds only when $AA^\dagger b = b$, so for an inconsistent $b$ the derivation of the normal equations (8) no longer goes through.

Editorial extensions

If this is right

  • At $\ell=1$, Algorithm 1 reproduces the classical randomized Kaczmarz method and the randomized average block Kaczmarz method as a boundary case.
  • At $\ell=\infty$ with no sketching, Algorithm 3 is exactly the conjugate gradient normal equation (CGNE) method, so the paper's analysis provides one convergence proof covering both extremes.
  • Increasing $\ell$ monotonically improves the expected contraction factor (Remark 3.5), letting the user trade per-iteration cost for a better convergence rate by keeping more history.
  • Setting $\ell\ge \mathrm{rank}(A)$ yields finite termination in at most $\mathrm{rank}(A)$ iterations in exact arithmetic, making the method a direct solver at that memory setting.
  • The IS-Krylov framework admits user-defined sketching distributions (partition, CountSketch, Gaussian, SRHT) without changing the convergence theory, so a fast sketch can be chosen on implementation grounds alone.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • An extension the paper leaves implicit is an adaptive schedule for $\ell$: start with a small memory length and increase it when progress slows, exploiting both the low per-iteration cost of small $\ell$ and the faster rate of large $\ell$; the numerical experiments here use only fixed values of $\ell$.
  • Because the $\ell=\infty$ limit is exactly CGNE, the new intermediate methods can be read as randomized truncated CGNE; a natural comparison (not made in the paper) is against truncated CG with preconditioning rather than only against other Kaczmarz-style methods.
  • The finite-termination guarantee in exact arithmetic suggests that in floating-point arithmetic the Gram-Schmidt formulation is the accuracy bottleneck; re-orthogonalizing the $p_i$ basis, or using the sketch to detect loss of orthogonality, is a stabilization the paper does not test.
  • If the duality between randomized Kaczmarz and randomized coordinate descent carries over to this setting, the same affine-subspace mechanism would give an RCD-Krylov bridge for least-squares problems, which the paper explicitly names as future work.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 3 minor

Summary. The paper proposes a unified affine-subspace projection framework for solving linear systems: each iterate is the Euclidean projection of A†b onto the affine span of the last ℓ iterates together with a sketched normal direction. With memory length ℓ=1 the scheme recovers randomized iterative methods such as randomized Kaczmarz; with ℓ=∞ and no sketching it reduces to a Krylov subspace method, specifically the CGNE recursion; intermediate ℓ yields new IS-Krylov algorithms. The authors prove affine independence of the search subspace, derive a conditional linear convergence bound in expectation with factor 1−q_kσ_min²(H^{1/2}A), establish finite termination when ℓ≥rank(A), give an O(nℓ) implementation via a tridiagonal inverse formula, and validate the methods on synthetic and real matrices.

Significance. For the consistent linear-systems case, the paper delivers a genuinely unifying view: the memory parameter ℓ interpolates between stochastic projection methods and deterministic Krylov methods, and the acceleration factor q_k is derived from the current iterates rather than fitted. The recovery of RK and of CGNE as limiting cases is a clean conceptual result, and the finite-termination statement for ℓ≥rank(A) is a useful theoretical property. The efficient implementation and the reproducible numerical study are additional strengths. The main weakness is that the consistency assumption is not carried through the problem statement, the algorithms, or the bridge claims, and the framework demonstrably breaks on inconsistent data.

major comments (3)
  1. [§3, Eq. (7)] The derivation of the normal-equation form (8) from (7) is valid only for consistent systems. The second equality in (7) replaces ⟨AᵀSSᵀ(Ax_k−b), x_k−A†b⟩ with ‖Sᵀ(Ax_k−b)‖², which is true exactly when A A†b = b, i.e., when b ∈ Range(A). For inconsistent b, the vector A(x_k−A†b) is not equal to Ax_k−b, so (8) is not equivalent to the geometric projection (2), and neither Algorithm 2 nor Algorithm 3 implements (2). Concretely, take A=[I₂;0] ∈ R^{3×2}, b=[0;0;1], S=e₃, x₀=0: then Sᵀ(Ax₀−b)=−1≠0, so Algorithm 1/3 accept this sketch, yet d₀=−AᵀSSᵀ(Ax₀−b)=0; Algorithm 1 has no solution to (8) and Algorithm 3 divides by zero in Step 3. The consistency assumption in Theorem 3.3 is therefore load-bearing and should appear in the statement of Algorithms 1–3 and in the abstract, or the analysis must be extended to inconsistent least-squares problems.
  2. [§4.3, CGNE recovery] The claim that Algorithm 3 with ℓ=∞ and Ω={I} is precisely CGNE requires the consistent-systems hypothesis. The simplification to the CGNE recursion uses Proposition 4.4, whose proof relies on identity (7); for inconsistent b the orthogonality relations fail, and the recursion can generate p_{k+1}=0 before reaching the least-squares solution. If CGNE is intended in the sense of the minimal-norm solution of a consistent underdetermined system, the statement should say so explicitly and should not be read as covering inconsistent least-squares problems, which the abstract and introduction currently suggest.
  3. [§5.1 and §6] Every numerical experiment constructs b=Ax∗, so the inconsistent case is never tested, and Section 6 explicitly defers the inconsistent case to future work on randomized coordinate descent. This is consistent with a paper whose theorems are for consistent systems, but it is not consistent with the unqualified language in the abstract and introduction about solving linear systems and bridging the two paradigms. The authors should either restrict the scope prominently or add an analysis of the least-squares case; the current framing overstates the reach of the framework.
minor comments (3)
  1. [§2.1] The notation for the vector decomposition is not typeset correctly and is hard to read; please define the (n−1)-dimensional prefix and the last coordinate with explicit symbols such as x̄ and x_n.
  2. [Remark 3.5] In the two displayed inequalities the symbol M appears in σ_min²(M^{1/2}A); this should be the matrix H from Theorem 3.3, since M is not defined in that remark.
  3. [Table 1] For matrices with reported σ_max/σ_min on the order of 10¹⁵–10¹⁷, the contraction bound of Theorem 3.3 would predict far slower progress than the reported iteration counts, and the use of b=Ax∗ in floating-point arithmetic may make the effective problem much better conditioned. Please clarify the numerical rank or singular-value distribution used, and state whether the reported condition numbers are computed by MATLAB's cond.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the randomized/Krylov identifications and convergence bounds are derived from the stated projections, not from fitted parameters or load-bearing self-citations.

full rationale

I walked the derivation chain. The framework is defined by the affine projection (2); the normal-equation form (6) is standard calculus, and the simplification to (8) relies on the orthogonality of x_k - A^†b to the previous affine subspace, which follows from the projection definition itself. The convergence theorem (Theorem 3.3) is proved from (6)-(8), Lemma 2.1, and the elementary inequality E[||S^T r||^2 / ||S^T A||^2] >= sigma_min^2(H^(1/2) A) ||x - A^†b||^2; the factor q_k is computed from the current iterates via (11), not fitted to experimental output. The Krylov connection is also derived: Lemma 4.1 proves Π_k = aff{x_{j_k}, ..., x_{k+1}} using the update (15), and Lemma 4.2 proves span{A^T r_0, ..., A^T r_k} = K_{k+1}(A^T A, A^T r_0) by induction from the recurrence r_{i+1} = r_i + δ_i A p_i; then Section 4.3 shows the ℓ = ∞, Ω = {I} case simplifies algebraically to the CGNE recurrences. None of these identifications assumes its conclusion. The self-citations to [67] for Lemmas 2.2-2.3 are elementary facts (B^T B v = 0 iff Bv = 0 under consistency, and E[SS^T] invertible plus E||S^T r||^2 = 0) and are not load-bearing; the lemmas from [38] and [52] are external and independently checkable. The skeptical concern that identity (7) and the while-loop condition require consistency is a genuine scope limitation, but it is not circularity; the paper states the consistency assumption in Theorem 3.3 and constructs all experiments with b = Ax*. I therefore find no step in which a prediction reduces by construction to its input.

Assumptions & free parameters 2 free parameters · 4 assumptions · 0 invented entities

The framework introduces no new postulated physical or mathematical entities. The only tunable quantities are algorithmic hyperparameters (ℓ and sketch size q); no free parameter is fitted to data to make the derivation work. The main restrictions come from the consistency assumption, the positive-definite sketching assumption, and standard external lemmas.

free parameters (2)
  • memory length ℓ = user-specified; experiments use ℓ=10 or 50
    Controls the affine subspace dimension and the interpolation between RK (ℓ=1) and Krylov (ℓ=infinity). No single value is used in the theory; the paper shows larger ℓ improves the bound.
  • sketch size q = user-specified; experiments use q=30, 50, 100, 300
    Number of rows or sketches per step; affects per-iteration cost and numerical performance but not the convergence factor directly.
assumptions (4)
  • domain assumption Assumption 2.1: E[SS^T] is positive definite for the sketching distribution.
    Needed for H = E[SS^T / ||S^T A||^2] to be positive definite and for the contraction factor in Theorem 3.3 to be meaningful.
  • domain assumption The linear system Ax = b is consistent.
    Theorem 3.3 assumes consistency, and equation (7) uses A A-dagger-b = b to write the normal equations as gamma_k e. The analysis does not cover inconsistent systems.
  • domain assumption Initial point x0 lies in Range(A^T).
    Used to keep all iterates in Range(A^T) and to justify finite termination; Remark 3.4 extends to arbitrary x0 by convergence to the projected solution x0-star.
  • standard math External lemmas: Lemma 2.1 from Lorenz-Winkler, Lemmas 2.2 and 2.3 from Zeng et al., Lemma 2.4 and Lemma 7.1 from Rieger.
    The paper relies on these cited results for positive-definiteness of H, null-step characterization, and the tridiagonal inverse formula. They are accepted as background and not rederived.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Connecting randomized iterative methods with Krylov subspaces." pith.science (2026). https://pith.science/paper/DGRSSBNZ

@misc{pith2026250520602,
  author       = {Pith},
  title        = {Pith review of: Connecting randomized iterative methods with Krylov subspaces},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/DGRSSBNZ}},
  note         = {Machine review of arXiv:2505.20602}
}
read the original abstract

Randomized iterative methods, such as the randomized Kaczmarz method, have gained significant attention for solving large-scale linear systems due to their simplicity and efficiency. Meanwhile, Krylov subspace methods have emerged as a powerful class of algorithms, known for their robust theoretical foundations and rapid convergence properties. Despite the individual successes of these two paradigms, their underlying connection has remained largely unexplored. In this paper, we develop a unified framework that bridges randomized iterative methods and Krylov subspace techniques, supported by both rigorous theoretical analysis and practical implementation. The core idea is to formulate each iteration as an adaptively weighted linear combination of the sketched normal vector and previous iterates, with the weights optimally determined via a projection-based mechanism. This formulation not only reveals how subspace techniques can enhance the efficiency of randomized iterative methods, but also enables the design of a new class of iterative-sketching-based Krylov subspace algorithms. We prove that our method converges linearly in expectation and validate our findings with numerical experiments.

Figures

Figures reproduced from arXiv: 2505.20602 by the authors.

Figure 1
Figure 1. The figures illustrate the evolution of RSE with respect to the number of iterations (top) and the CPU time (bottom). The title of each subplot indicates the corresponding values of κ and r. The other parameters are fixed as m = 5000, n = 1000, q = 30, and ℓ = 10. All computations are terminated once RSE< 10−12 . presented in [PITH_FULL_IMAGE:figures/full_fig_p026_1.png] view at source ↗
Figure 2
Figure 2. Figures depict the evolution of RSE with respect to the number of iterations (top) and the CPU time (bottom). The title of each plot indi￾cates the values of κ and r. We set m = 256, n = 128, q = 30, and ℓ = 10. All computations are terminated once the number of iterations exceeds a certain limit. IS-Krylov-PS, IS-Krylov-CS, IS-Krylov-GS, and IS-Krylov-SRHT [PITH_FULL_IMAGE:figures/full_fig_p027_2.png] view at source ↗
Figure 3
Figure 3. Figures depict the evolution of the number of full iterations (top) and the CPU time (bottom) with respect to the block size q and the number of previous iterations ℓ. The title of each plot indicates the values of κ and r. We set m = 1024 and n = 128. All computations are terminated once RSE< 10−12 . aloi, cod-rna, and protein. This selection covers a range of matrix properties, includ￾ing full-rank and rank-defici… view at source ↗
Figures from the paper (3 more)
Figure 4
Figure 4. Figure 4: Figures depict the evolution of RSE with respect to the number of iterations (top) and the CPU time (bottom). The title of each plot indi￾cates the values of κ and r. We set m = 10000, n = 5000, and q = 100, and for IS-Krylov-PS, we set ℓ = 50. All computations are ter…
Figure 5
Figure 5. Figure 5: Performance of RABK, SCGP, and IS-Krylov-PS for linear sys￾tems with coefficient matrices from LIBSVM [5]. Figures depict the evolution of RSE with respect to the number of iterations and the CPU time. Each plot title indicates the dataset name and data dimensions. We …
Figure 6
Figure 6. Figure 6: Figures depict the CPU time (in seconds) versus increasing num￾ber of rows. The title of each plot indicates the values of n, κ and ℓ. We set q = 50. derived efficient implementation schemes for the algorithm and proposed a novel iterative￾sketching-based Krylov subspa…

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Enhanced randomized Douglas-Rachford method: Improved probabilities and adaptive momentum

    math.NA 2025-06 reject novelty 6.0 of 10

    A randomized Douglas-Rachford variant with without-replacement or volume sampling and adaptive momentum converges linearly in expectation and is faster in practice.

Reference graph

Works this paper leans on

70 extracted references · 45 canonical work pages · cited by 1 Pith paper

  1. [1]

    Randomized Gram-Schm idt process with application to GMRES

    Oleg Balabanov and Laura Grigori. Randomized Gram-Schm idt process with application to GMRES. SIAM Journal on Scientific Computing , 44(3):A1450–A1474, 2022

    work page 2022

  2. [2]

    Pattern recognition and machine learning

    Christopher M Bishop and Nasser M Nasrabadi. Pattern recognition and machine learning . Springer, 2006

    2006

  3. [3]

    Introduction to applied linear algebra: vectors, matrices , and least squares

    Stephen Boyd and Lieven Vandenberghe. Introduction to applied linear algebra: vectors, matrices , and least squares. Cambridge university press, 2018

    2018

  4. [4]

    Gmres with randomized sketching and deflated restarting

    Liam Burke, Stefan G¨ uttel, and Kirk M Soodhalter. Gmres with randomized sketching and deflated restarting. SIAM Journal on Matrix Analysis and Applications , 46(1):702–725, 2025

    work page 2025

  5. [5]

    Libsvm: a library for support vector machines

    Chih-Chung Chang and Chih-Jen Lin. Libsvm: a library for support vector machines. ACM transactions on intelligent systems and technology (TIST) , 2(3):1–27, 2011

    work page 2011

  6. [6]

    Finding frequent items in data streams.Theor

    Moses Charikar, Kevin Chen, and Martin Farach-Colton. Finding frequent items in data streams.Theor. Comput. Sci. , 312(1):3–15, 2004

    work page 2004

  7. [7]

    Regularized Kaczmarz algorith ms for tensor recovery

    Xuemei Chen and Jing Qin. Regularized Kaczmarz algorith ms for tensor recovery. SIAM Journal on Imaging Sciences, 14(4):1439–1471, 2021

    2021

  8. [8]

    Low-rank approxi mation and regression in input sparsity time

    Kenneth L Clarkson and David P Woodruff. Low-rank approxi mation and regression in input sparsity time. J. ACM , 63(6):1–45, 2017

    work page 2017

Show all 70 references
  1. [9]

    An improved data stream summary: the count-min sketch and its applications

    Graham Cormode and Shan Muthukrishnan. An improved data stream summary: the count-min sketch and its applications. J. Algorithms, 55(1):58–75, 2005. CONNECTING RIM AND KRYLOV SUBSPACES 33

    2005

  2. [10]

    Recent and upcoming developments in randomized nu- merical linear algebra for machine learning

    Micha/suppress l Derezi´ nski and Michael W Mahoney. Recent and upcoming developments in randomized nu- merical linear algebra for machine learning. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining , pages 6470–6479, 2024

    2024

  3. [11]

    Unified matrix treatment of the fast wal sh-hadamard transform

    Fino and Algazi. Unified matrix treatment of the fast wal sh-hadamard transform. IEEE Trans. Com- puters, 100(11):1142–1146, 1976

    1976

  4. [12]

    Ri dgeSketch: a fast sketching based solver for large scale ridge regression

    Nidham Gazagnadou, Mark Ibrahim, and Robert M Gower. Ri dgeSketch: a fast sketching based solver for large scale ridge regression. SIAM Journal on Matrix Analysis and Applications , 43(3):1440–1468, 2022

    2022

  5. [13]

    Acceleration schemes for the method of alternating projections

    William B Gearhart and Mathew Koshy. Acceleration schemes for the method of alternating projections. Journal of Computational and Applied Mathematics , 26(3):235–249, 1989

    1989

  6. [14]

    Matrix computations

    Gene H Golub and Charles F Van Loan. Matrix computations. John Hopkins University Press, Balti- more, MD, 4th edition, 2012

    2012

  7. [15]

    Richard Gordon, Robert Bender, and Gabor T. Herman. Alg ebraic reconstruction techniques (ART) for three-dimensional electron microscopy and X-ray photo graphy. J. Theor. Biol. , 29(3):471–481, De- cember 1970

    1970

  8. [16]

    Gower and Peter Richt´ arik

    Robert M. Gower and Peter Richt´ arik. Randomized itera tive methods for linear systems. SIAM J. Matrix Anal. Appl. , 36(4):1660–1690, 2015

    2015

  9. [17]

    A sketch-and-select Arnoldi process

    Stefan G¨ uttel and Igor Simunec. A sketch-and-select Arnoldi process. SIAM Journal on Scientific Com- puting, 46(4):A2774–A2797, 2024

    2024

  10. [18]

    Randomized Doug las–Rachford methods for linear systems: Improved accuracy and efficiency

    Deren Han, Yansheng Su, and Jiaxin Xie. Randomized Doug las–Rachford methods for linear systems: Improved accuracy and efficiency. SIAM Journal on Optimization , 34(1):1045–1070, 2024

    2024

  11. [19]

    Randomized Doug las-Rachford methods for linear systems: Improved accuracy and efficiency

    Deren Han, Yansheng Su, and Jiaxin Xie. Randomized Doug las-Rachford methods for linear systems: Improved accuracy and efficiency. SIAM J. Optim. , 34(1):1045–1070, 2024

    2024

  12. [20]

    On pseudoinverse-free random ized methods for linear systems: Unified framework and acceleration

    Deren Han and Jiaxin Xie. On pseudoinverse-free random ized methods for linear systems: Unified framework and acceleration. arXiv preprint arXiv:2208.05437 , 2022

    2022 arXiv

  13. [21]

    The elements of statistical learning: data mining, inference, and prediction, 2009

    Trevor Hastie, Robert Tibshirani, and Jerome Friedman . The elements of statistical learning: data mining, inference, and prediction, 2009

    2009

  14. [22]

    Inertial ra ndomized kaczmarz algorithms for solving coherent linear systems

    Songnian He, Ziting Wang, and Qiao-Li Dong. Inertial ra ndomized kaczmarz algorithms for solving coherent linear systems. Numerical Algorithms, pages 1–31, 2024

    2024

  15. [23]

    Rows v ersus columns: Randomized Kaczmarz or Gauss–Seidel for ridge regression

    Ahmed Hefny, Deanna Needell, and Aaditya Ramdas. Rows v ersus columns: Randomized Kaczmarz or Gauss–Seidel for ridge regression. SIAM Journal on Scientific Computing , 39(5):S528–S542, 2017

    2017

  16. [24]

    Generalized Gearhart-Koshy acceleration is a Krylov space method of a new type

    Markus Hegland and Janosch Rieger. Generalized Gearhart-Koshy acceleration is a Krylov space method of a new type. arXiv preprint arXiv:2311.18305 , 2023

    2023 arXiv

  17. [25]

    Algebraic reconstruction techniques can be made computation- ally efficient (positron emission tomography application)

    Gabor T Herman and Lorraine B Meyer. Algebraic reconstruction techniques can be made computation- ally efficient (positron emission tomography application). IEEE Trans. Medical Imaging, 12(3):600–609, 1993

    1993

  18. [26]

    Randomized K aczmarz in adversarial distributed setting

    Longxiu Huang, Xia Li, and Deanna Needell. Randomized K aczmarz in adversarial distributed setting. SIAM Journal on Scientific Computing , 46(3):B354–B376, 2024

    2024

  19. [27]

    Linear convergence of randomized Kaczmarz method for solving complex- valued phaseless equations

    Meng Huang and Yang Wang. Linear convergence of randomized Kaczmarz method for solving complex- valued phaseless equations. SIAM Journal on Imaging Sciences , 15(2):989–1016, 2022

    2022

  20. [28]

    Linear convergence of reshuffling Kaczmarz methods with sparse constraints

    Halyun Jeong and Deanna Needell. Linear convergence of reshuffling Kaczmarz methods with sparse constraints. arXiv preprint arXiv:2304.10123, to appear in SIAM Journal on Scientific Computing , 2023

    2023 arXiv

  21. [29]

    Extensi ons of lipschitz mappings into a hilbert space

    William B Johnson, Joram Lindenstrauss, et al. Extensi ons of lipschitz mappings into a hilbert space. Contemporary mathematics, 26(189-206):1, 1984

    1984

  22. [30]

    Angen¨ aherte aufl¨ osung von systemen linearer glei-chungen

    S Karczmarz. Angen¨ aherte aufl¨ osung von systemen linearer glei-chungen. Bull. Int. Acad. Pol. Sic. Let., Cl. Sci. Math. Nat. , pages 355–357, 1937

    1937

  23. [31]

    The suitesparse matrix collection website interface

    Scott P Kolodziej, Mohsen Aznaveh, Matthew Bullock, Ja rrett David, Timothy A Davis, Matthew Henderson, Yifan Hu, and Read Sandstrom. The suitesparse matrix collection website interface. Journal of Open Source Software , 4(35):1244, 2019

    2019

  24. [32]

    First-order and stochastic optimization methods for machi ne learning

    Guanghui Lan. First-order and stochastic optimization methods for machi ne learning. Springer, 2020. 34 YONGHAN SUN, DEREN HAN, AND JIAXIN XIE

    2020

  25. [33]

    Randomized method s for linear constraints: convergence rates and conditioning

    Dennis Leventhal and Adrian S Lewis. Randomized method s for linear constraints: convergence rates and conditioning. Math. Oper. Res. , 35(3):641–654, 2010

    2010

  26. [34]

    Numerical Mathe- matics and Scie, 2013

    J¨ org Liesen and Zdenek Strakos.Krylov subspace methods: principles and analysis . Numerical Mathe- matics and Scie, 2013

    2013

  27. [35]

    An accelerated randomized Kaczmarz algorithm

    Ji Liu and Stephen Wright. An accelerated randomized Kaczmarz algorithm. Math. Comp., 85(297):153– 178, 2016

    2016

  28. [36]

    Subspace methods for nonlinear optimization

    Xin Liu, Zaiwen Wen, and Ya-Xiang Yuan. Subspace methods for nonlinear optimization. CSIAM Trans. Appl. Math. , 2(4):585–651, 2021

    2021

  29. [37]

    Momentum and stoc hastic momentum for stochastic gradient, newton, proximal point and subspace descent methods

    Nicolas Loizou and Peter Richt´ arik. Momentum and stoc hastic momentum for stochastic gradient, newton, proximal point and subspace descent methods. Computational Optimization and Applications , 77(3):653–710, 2020

    2020

  30. [38]

    Minimal error mom entum bregman-kaczmarz

    Dirk A Lorenz and Maximilian Winkler. Minimal error mom entum bregman-kaczmarz. Linear Algebra and its Applications , 709:416–448, 2025

    2025

  31. [39]

    Randomized Kaczmarz for ten sor linear systems

    Anna Ma and Denali Molitor. Randomized Kaczmarz for ten sor linear systems. BIT Numerical Math- ematics, 62(1):171–194, 2022

    2022

  32. [40]

    Stochastic gradient descent for linear systems with missing data

    Anna Ma and Deanna Needell. Stochastic gradient descent for linear systems with missing data. Numer. Math. Theory Methods Appl. , 12(1):1–20, 2019

    2019

  33. [41]

    Randomized num erical linear algebra: Foundations and algorithms

    Per-Gunnar Martinsson and Joel A Tropp. Randomized num erical linear algebra: Foundations and algorithms. Acta Numerica, 29:403–572, 2020

    2020

  34. [42]

    LSRN: A parallel iterative solver for strongly over-or underdetermined systems

    Xiangrui Meng, Michael A Saunders, and Michael W Mahone y. LSRN: A parallel iterative solver for strongly over-or underdetermined systems. SIAM J. Sci. Comput. , 36(2):C95–C118, 2014

    2014

  35. [43]

    Fast and accurate ran domized algorithms for linear systems and eigenvalue problems

    Yuji Nakatsukasa and Joel A Tropp. Fast and accurate ran domized algorithms for linear systems and eigenvalue problems. SIAM Journal on Matrix Analysis and Applications , 45(2):1183–1214, 2024

    2024

  36. [44]

    Faster randomized block kaczmarz algorit hms

    Ion Necoara. Faster randomized block kaczmarz algorit hms. SIAM Journal on Matrix Analysis and Applications, 40(4):1425–1452, 2019

    2019

  37. [45]

    Stocha stic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm

    Deanna Needell, Nathan Srebro, and Rachel Ward. Stocha stic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm. Math. Program., 155:549–573, 2016

    2016

  38. [46]

    Introductory lectures on convex optimization: A basic cour se, volume 87

    Yurii Nesterov. Introductory lectures on convex optimization: A basic cour se, volume 87. Springer Sci- ence & Business Media, Berlin, 2003

    2003

  39. [47]

    A method for solving the convex programming problem with convergence rate O(1/k2)

    Yurii E Nesterov. A method for solving the convex programming problem with convergence rate O(1/k2). In Dokl. akad. nauk Sssr , volume 269, pages 543–547, 1983

    1983

  40. [48]

    Numerical optimization

    Jorge Nocedal and Stephen J Wright. Numerical optimization. Springer, 1999

    1999

  41. [49]

    Iterative hessia n sketch: Fast and accurate solution approxi- mation for constrained least-squares

    Mert Pilanci and Martin J Wainwright. Iterative hessia n sketch: Fast and accurate solution approxi- mation for constrained least-squares. Journal of Machine Learning Research , 17(53):1–38, 2016

    2016

  42. [50]

    Some methods of speeding up the converge nce of iteration methods

    Boris T Polyak. Some methods of speeding up the converge nce of iteration methods. Comput. Math. Math. Phys. , 4(5):1–17, 1964

    1964

  43. [51]

    A statistical p erspective on randomized sketching for ordi- nary least-squares

    Garvesh Raskutti and Michael W Mahoney. A statistical p erspective on randomized sketching for ordi- nary least-squares. Journal of Machine Learning Research , 17(213):1–31, 2016

    2016

  44. [52]

    Generalized gearhart-koshy accelera tion for the kaczmarz method

    Janosch Rieger. Generalized gearhart-koshy accelera tion for the kaczmarz method. Mathematics of Computation, 92(341):1251–1272, 2023

    2023

  45. [53]

    A stochastic approxi mation method

    Herbert Robbins and Sutton Monro. A stochastic approxi mation method. Ann. Math. Statistics , pages 400–407, 1951

    1951

  46. [54]

    Iterative methods for sparse linear systems

    Yousef Saad. Iterative methods for sparse linear systems . SIAM, 2003

    2003

  47. [55]

    Linear convergence o f the randomized sparse Kaczmarz method

    Frank Sch¨ opfer and Dirk A Lorenz. Linear convergence o f the randomized sparse Kaczmarz method. Math. Program., 173(1):509–536, 2019

    2019

  48. [56]

    A randomized Kacz marz algorithm with exponential conver- gence

    Thomas Strohmer and Roman Vershynin. A randomized Kacz marz algorithm with exponential conver- gence. Journal of Fourier Analysis and Applications , 15(2):262–278, 2009

    2009

  49. [57]

    On greedy multi-step inertial randomized kaczmarz method for solving linear systems

    Yansheng Su, Deren Han, Yun Zeng, and Jiaxin Xie. On greedy multi-step inertial randomized kaczmarz method for solving linear systems. Calcolo, 61(4):68, 2024

    2024

  50. [58]

    Gearhart–Koshy acceleration for affine su bspaces

    Matthew K Tam. Gearhart–Koshy acceleration for affine su bspaces. Operations Research Letters , 49(2):157–163, 2021. CONNECTING RIM AND KRYLOV SUBSPACES 35

    2021

  51. [59]

    Phase retrieval via randomized Kaczmarz: theoretical guarantees

    Yan Shuo Tan and Roman Vershynin. Phase retrieval via randomized Kaczmarz: theoretical guarantees. Information and Inference: A Journal of the IMA , 8(1):97–123, 2019

    2019

  52. [60]

    Improved analysis of the subsampled randomized hadamard transform

    Joel A Tropp. Improved analysis of the subsampled randomized hadamard transform. Adv. Adapt. Data Anal.,, 3(01n02):115–126, 2011

    2011

  53. [61]

    A fast randomized algorithm for the approximation of matrices

    Franco Woolfe, Edo Liberty, Vladimir Rokhlin, and Mark Tygert. A fast randomized algorithm for the approximation of matrices. Appl. Comput. Harmon. Anal. , 25(3):335–366, 2008

    2008

  54. [62]

    Randomized blo ck kaczmarz with volume sampling: Momen- tum acceleration and efficient implementation

    Ruike Xiang, Jiaxin Xie, and Qiye Zhang. Randomized blo ck kaczmarz with volume sampling: Momen- tum acceleration and efficient implementation. arXiv preprint arXiv:2503.13941 , 2025

    2025 arXiv

  55. [63]

    Randomized iterat ive methods for generalized absolute value equations: Solvability and error bounds

    Jiaxin Xie, Houduo Qi, and Deren Han. Randomized iterat ive methods for generalized absolute value equations: Solvability and error bounds. arXiv preprint arXiv:2405.04091 , 2024

    2024 arXiv

  56. [64]

    A review on subspace methods for nonline ar optimization

    Ya-xiang Yuan. A review on subspace methods for nonline ar optimization. In Proceedings of the Inter- national Congress of Mathematics , pages 807–827, 2014

    2014

  57. [65]

    Ada ptively sketched Bregman projection methods for linear systems

    Zi-Yang Yuan, Lu Zhang, Hongxia Wang, and Hui Zhang. Ada ptively sketched Bregman projection methods for linear systems. Inverse Problems, 38(6):065005, 2022

    2022

  58. [66]

    Random ized Kaczmarz method with adaptive stepsizes for inconsistent linear systems

    Yun Zeng, Deren Han, Yansheng Su, and Jiaxin Xie. Random ized Kaczmarz method with adaptive stepsizes for inconsistent linear systems. Numer. Algor. , 94:1403–1420, 2023

    2023

  59. [67]

    On adap tive stochastic heavy ball momentum for solving linear systems

    Yun Zeng, Deren Han, Yansheng Su, and Jiaxin Xie. On adap tive stochastic heavy ball momentum for solving linear systems. SIAM Journal on Matrix Analysis and Applications , 45(3):1259–1286, 2024

    2024

  60. [68]

    Proof of the main results 7.1

    Appendix. Proof of the main results 7.1. Proof of Lemma 3.7. The following lemma is useful for proving Lemma 3.7. Lemma 7.1 ( [ 52], Lemma 12) . Suppose the matrix B =∑ n j=1 αj /BD j n( /BD j n)⊤ with αj ⁄= 0 for j = 1, . . . , n. Then the matrix C(α1, . . . , αn), as defined ...

  61. [69]

    By the arbitrariness of x, we conclude Kk+1(A⊤A, A⊤r0) ⊆ Hk

    where we have (A⊤A)kA⊤r0 = 1 λk−1 k−1  A⊤rk − A⊤r0 − k−2∑ j=0 λi j(A⊤A)j+1A⊤r0   , which is well-defined as λk−1 k−1 ⁄= 0. By the arbitrariness of x, we conclude Kk+1(A⊤A, A⊤r0) ⊆ Hk. Hence, we can conclude that Hk = Kk+1(A⊤A, A⊤r0). This completes the proof of the lemma. □...

  62. [70]

    □ Proof of Proposition 4.4

    This completes the proof of the theorem. □ Proof of Proposition 4.4. (i) Since jk ≤ t < v ≤ k, we have (23) ⟨pv, pt⟩ = ⟨xv+1 − xv, xt+1 − xt⟩ δvδt = ⟨xv+1 − A†b, xt+1 − xt⟩ δvδt + ⟨A†b − xv, xt+1 − xt⟩ δvδt = ⟨xv+1 − A†b, xt+1 − xv+1⟩ δvδt + ⟨xv+1 − A†b, xv+1 − xt⟩ δvδt + ⟨A†b...

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.