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

Deren Han; Jiaxin Xie; Liqi Guo; Ruike Xiang

REVIEW 2 major objections 6 minor 43 references

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

T0 review · 2 major / 6 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 Two smarter row-sampling rules and a tuning-free adaptive momentum scheme give the randomized Douglas-Rachford method provably faster linear convergence for consistent linear systems.

desk verdict Solid algorithmic contribution with strong numerics, but the main convergence theorems use an undefined M^{1/2} for a nonsymmetric M; fixable but currently load-bearing. read the letter →

arxiv 2506.10261 v1 pith:LGOGUPOD submitted 2025-06-12 math.NA cs.NA

Liqi Guo , Ruike Xiang , Deren Han , Jiaxin Xie This is my paper · ORCID

classification math.NAcs.NA MSC 65F1065F2090C2515A0668W20

keywords randomizedDouglas-Rachfordlinearsystemswithout-replacementsamplingvolumeadaptiveheavy-ballmomentumconvergenceKaczmarz-typemethods

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 the randomized Douglas-Rachford (RDR) method for consistent linear systems can be made substantially faster by replacing its with-replacement row sampling. The proposed PRDR method instead draws the pair of reflection hyperplanes without replacement, or by volume sampling that favors geometrically diverse rows, and the paper proves linear convergence in expectation with a contraction factor that is sharper than the original RDR bound in the cases it analyzes. On top of that, the AmPRDR method adds a heavy-ball momentum term whose step size and momentum coefficient are recomputed at every iteration from the last two iterates, removing the need to tune them. The numerical experiments show the enhanced methods consistently outperform RDR and its fixed-momentum variant, with the largest gains when row norms differ strongly or hyperplane angles are pronounced.

What carries the argument

The engine is the expected one-step operator made by composing two hyperplane reflections. Writing the reflection through row $i$ as $T_{H_i}=I-2a_i a_i^\top/\|a_i\|_2^2$, Strategy I gives $E[T_{H_{i_2}}T_{H_{i_1}}]=I-\frac{2}{\|A\|_F^2}A^\top M A$, and Strategy II gives $I-\frac{4}{\|A\|_F^4-\|AA^\top\|_F^2}A^\top N A$; the proof then extracts contraction from the smallest nonzero singular value of $M^{1/2}A$ (or $N^{1/2}A$) using the fact that every iterate error lies in $\mathrm{Range}(A^\top)$. For the adaptive momentum variant, the auxiliary construction $\tilde{x}_{k+1}=\frac12 x_k+\frac12 z_k$ and the vector $\zeta_k=\langle z_k-x_k,x_k-x_{k-1}\rangle(z_k-x_k)-\|z_k-x_k\|_2^2(x_k-x_{k-1})$ turn the per-step gain into the angle factor $\gamma_k=\inf_{(i,j)\in Q_k}\cos^2\theta_k$, and the exact least-squares formulas (8) for $\alpha_k,\beta_k$ are computable because $\langle x_k-x_0^*, x_k-x_{k-1}\rangle=0$.

What would settle it

Take a consistent $3\times2$ system whose rows have unequal norms, form $M$ by (3), and test whether $M_{12}=M_{21}$. The displayed formula gives $M_{12}=2\langle a_1,a_2\rangle/(\|A\|_F^2-\|a_2\|_2^2)$ while $M_{21}=2\langle a_1,a_2\rangle/(\|A\|_F^2-\|a_1\|_2^2)$, so for unequal row norms the matrix is asymmetric and $M^{1/2}$ in Theorem 3.2 is not defined; simulating PRDR-I on such a system and comparing the observed contraction with the claimed factor would settle whether the rate should be restated in terms of $A^\top M A$ instead.

Watch

Extended reading notes

Core claim

The central claim is Theorem 3.2: for a consistent system $Ax=b$ with $\mathrm{rank}(A)\ge 2$ and relaxation $\alpha\in(0,1)$, PRDR with without-replacement sampling satisfies $E[\|x_k-x_0^*\|_2^2]\le \left(1-\frac{4\alpha(1-\alpha)\sigma_{\min}^2(M^{1/2}A)}{\|A\|_F^2}\right)^k\|x_0-x_0^*\|_2^2$, and with volume sampling it satisfies $E[\|x_k-x_0^*\|_2^2]\le \left(1-\frac{8\alpha(1-\alpha)\sigma_{\min}^2(N^{1/2}A)}{\|A\|_F^4-\|AA^\top\|_F^2}\right)^k\|x_0-x_0^*\|_2^2$. Theorem 4.3 extends both rates to AmPRDR by multiplying the base contraction by $(1-\gamma_k)$, where $\gamma_k$ is the smallest squared cosine of a certain angle determined by the current iterate and the previous displacement. For row-normalized matrices the paper shows the PRDR-I contraction factor is strictly tighter than the RDR bound in (2), and for row-normalized, row-orthogonal matrices PRDR-II reaches the factor $1-2\sigma_{\min}^2(A)/\|A\|_F^2$. The mechanism is that the expected composition of the two random reflections becomes $I-\frac{2}{\|A\|_F^2}A^\top M A$ under Strategy I and $I-\frac{4}{\|A\|_F^4-\|AA^\top\|_F^2}A^\top N A$ under Strategy II, with $M$ and $N$ positive definite.

Load-bearing premise

The convergence-rate proof for the without-replacement strategy uses $M^{1/2}$, but the matrix $M$ in (3) has asymmetric off-diagonal entries (the denominator changes with the column index), so $M$ need not be symmetric positive definite and the displayed rate is not well-defined for a general matrix $A$.

Editorial extensions

If this is right

For row-normalized systems with $\alpha=1/2$, the PRDR-I bound is strictly tighter than the original RDR bound, so the without-replacement rule alone gives a provable worst-case speedup.
For row-normalized, row-orthogonal systems, volume sampling reaches the factor $1-2\sigma_{\min}^2(A)/\|A\|_F^2$, the same contraction as randomized Kaczmarz under that normalization.
AmPRDR requires no user-tuned relaxation or momentum parameters, and its contraction is the PRDR contraction multiplied by $(1-\gamma_k)$, so the adaptive momentum cannot worsen the worst-case factor.
The predicted gains are largest when row norms vary strongly or hyperplanes are nearly parallel, the regime where with-replacement sampling repeatedly picks the same rows.
Because the volume-sampling distribution depends only on $A$, the precomputed sampling costs can be amortized over many right-hand sides for the same coefficient matrix.

Reading between the lines

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

The explicit parameter formulas in (8) compute an exact least-squares step over the two-dimensional span of the latest reflection direction and the previous displacement; a natural test is whether, averaged over random draws, these directions approximate a Krylov subspace and whether the method inherits any finite-convergence property in exact arithmetic.
Because the volume-sampling distribution depends only on $A$, the same precomputed sampling table can be reused for many right-hand sides, making AmPRDR-II attractive for sequences of linear systems with a fixed matrix and changing data, a setting the paper does not test.
The same adaptive-momentum recipe should transplant to other two-reflection stochastic algorithms and to randomized coordinate methods, since the only ingredient needed is a cheap residual inner product of the form used in (8).

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.

Desk Editor's Note

read the letter

Short version: the algorithms are worth knowing about, and the numerics are promising, but the main theorems as stated aren't well-defined. The matrix M in (3) is not symmetric—off-diagonal entries have denominators depending on the column index—so M^{1/2} and σ_min(M^{1/2}A) don't make sense. The proof of Proposition 3.1 actually establishes x^T M x > 0, i.e. the symmetric part is SPD, not that M is symmetric positive definite. This is an internal inconsistency with their own Section 2.1. Since Theorem 3.2 and Theorem 4.3 rely on M^{1/2}, the central convergence guarantees are not rigorously established as written.

The good news is that this looks fixable. The quadratic form A^T M A only enters through the symmetric part, so replacing M by S=(M+M^T)/2 would make the bounds well-defined and the core argument in Lemma 7.1 and the proof of Theorem 3.2 would likely go through. The range inclusion step also needs a small adjustment, but it's the same idea. So the paper has a serious but largely notational flaw at the center of its theory.

What's genuinely new: combining without-replacement and volume sampling with RDR, and the adaptive heavy-ball momentum that eliminates tuning. The without-replacement trick is simple and shows real gains when row norms vary; the volume sampling is principled and the experiments support it. The comparison with the prior RDR bound is only performed in special cases (row-normalized, or row-normalized with orthogonal rows), so the abstract's claim of 'stronger convergence guarantees' is broader than what is proven. The adaptive momentum theorem has a similar issue, and γ_k could be zero or tiny, so the improvement over PRDR is not guaranteed to be strict. These are secondary but worth fixing too.

The numerics are credible: the proposed methods consistently beat RDR and a well-tuned mRDR on the synthetic tests, and on SuiteSparse the adaptive momentum methods are competitive with tuned mRDR while being parameter-free. That is a solid practical contribution.

My recommendation: send it to peer review, but require a major revision focused on the M^{1/2} issue and on scoping the claims. The algorithmic kernel is worth refereeing; the current write-up is not.

Referee Report

2 major / 6 minor

Summary. The paper proposes two enhancements to the randomized Douglas–Rachford (RDR) method for consistent linear systems: a "practical RDR" (PRDR) method that uses either without-replacement sampling or volume sampling (Algorithm 1), and an adaptive-momentum variant (AmPRDR, Algorithm 2) that determines the relaxation and momentum parameters at each iteration by solving a local least-squares problem. The main theoretical claims are Theorems 3.2 and 4.3, which assert linear convergence in expectation with rates expressed in terms of sigma_min(M^{1/2}A) and sigma_min(N^{1/2}A), where M and N are defined in Eqs. (3) and (4). Numerical experiments on synthetic and SuiteSparse matrices compare the proposed methods with RDR and momentum RDR.

Significance. If the convergence claims were rigorously established, the paper would constitute a useful contribution to randomized iterative methods: the sampling strategies are natural, the adaptive momentum removes manual tuning, and the numerical study is reasonably broad. The appendix contains detailed derivations, and the experiments cover both synthetic and real-world matrices. However, the central theorems are currently not well-defined because the matrix M in Eq. (3) is not symmetric in general, so M^{1/2} and sigma_min(M^{1/2}A) are not standard objects. The flaw appears local and repairable by replacing M with its symmetric part, so the underlying idea is defensible, but the stated results do not hold as written.

major comments (2)

[Eq. (3), Theorems 3.2 and 4.3, Appendix 7.1] The matrix M in Eq. (3) is not symmetric in general: its off-diagonal entry is -2<a_i,a_j>/(||A||_F^2 - ||a_j||^2), with the denominator depending on the column index j, so M_ij != M_ji. For example, with rows a1=(1,0) and a2=(1,1), one gets M_12=-2 and M_21=-1. Since Section 2.1 defines positive definiteness only for symmetric matrices, Proposition 3.1 proves at most that the symmetric part \bar{M}=(M+M^T)/2 is positive definite. Consequently, M^{1/2} and sigma_min(M^{1/2}A) in Theorems 3.2 and 4.3 are not defined for a general coefficient matrix, and the proof step in Appendix 7.1, "Since M is positive definite, x_k - x_0^* lies in Range(A^T M^{1/2})", is unsupported. The theorems should be restated with \bar{M}^{1/2} (which is legitimate because Lemma 7.1's expectation only involves A^T M A = A^T \bar{M} A). This is a load-bearing issue for the paper's central convergence claims.
[Definition 2.1, Strategy II, Lemma 7.1] Volume sampling is defined on unordered subsets S in ([m] choose 2), but Strategy II in Algorithm 1 and Algorithm 2 uses an ordered pair (i_{k1}, i_{k2}) to form the composition R_{H_{i_{k2}}} R_{H_{i_{k1}}}. The paper does not specify how the two indices of the sampled subset are ordered. Lemma 7.1 implicitly assumes that each ordered pair (i,j) with i != j is selected with probability (||a_i||^2 ||a_j||^2 - <a_i,a_j>^2)/(||A||_F^4 - ||AA^T||_F^2), which corresponds to choosing the order uniformly at random after volume sampling. Without this specification, the expectation computed in Lemma 7.1 is not the expectation of the algorithm's update, so Theorem 3.2's Strategy II bound is not correctly attached to Algorithm 1 as written. The algorithm should explicitly state the randomization of the order, or the proof should be adapted to the specified ordering.

minor comments (6)

[Abstract and Section 3.1] The abstract and introduction claim "stronger convergence guarantees" and "improved convergence bounds" without qualification, but the only theoretical comparison with the RDR bound in Eq. (2) is carried out under restrictive assumptions: row-normalized rows for Strategy I, and row-normalized plus orthogonal rows for Strategy II. This limitation should be stated in the abstract or introduction.
[Section 2.1] The text contains a typo: "spectual norm" should be "spectral norm".
[Algorithm 1] The input line says x0 in R^m, but the iterates and initial vector should be in R^n, consistent with the linear system A in R^{m x n}.
[Appendix 7.1, proof of Lemma 7.1] In the last displayed equation of the Strategy II calculation, the text says "matrix N = G - \bar{G} is given by (3)", but N is defined in Eq. (4), not Eq. (3).
[Section 4, Eq. (9)] The notation theta_k in Eq. (9) is overloaded: the angle between \tilde{x}_{k+1}-x_0^* and zeta_k depends on the selected pair (i,j) through z_k. The definition should use theta_k^{(i,j)} or an equivalent explicit dependence, with gamma_k defined as the infimum over pairs.
[Proof of Proposition 4.1] The phrase "Without loss of generality, we assume that the two residuals have the same sign" is not fully justified, because the two residuals play different roles in the definitions of u_k and v_k. The argument should either explain the symmetry or handle both sign cases explicitly.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the improved sampling and adaptive-momentum rates are derived from explicit expectation computations, with prior-work citations used only as auxiliary lemmas rather than as the target result.

full rationale

The paper's new results are derived rather than assumed. Theorem 3.2 follows by computing the expected composition E[T_Hj T_Hi] explicitly under Strategies I and II (Lemma 7.1), which introduces the matrices M and N in Eqs. (3)-(4) by algebra; the contraction rate is then obtained by applying the elementary identity in [12, Lemma A.2] and the range invariance in [12, Lemma A.3]. Those cited lemmas are not the target rate, are parameter-free algebraic facts, and do not presuppose without-replacement or volume sampling; their use is therefore independent support rather than circularity. The baseline bound (2) from [12] serves only as a comparison benchmark, not as an ingredient of the proof. Theorem 4.3 similarly derives the adaptive momentum update as the minimizer of the least-squares problem (6), which makes x_{k+1} the orthogonal projection of x0* onto PI_k; the factor (1 - gamma_k) is defined from the actual angle cos^2(theta_k) of the iterate geometry and is not a fitted parameter, and the remaining factor is the one-step version of Theorem 3.2. No prediction in the paper is obtained by fitting a parameter to the quantity it later predicts, and no uniqueness or ansatz is imported from the authors' prior work. The nonsymmetry of M in Eq. (3) (off-diagonal denominators depend on the column index, so M^{1/2} and sigma_min(M^{1/2}A) are not standard objects) is a serious correctness and well-definedness flaw, but it is a rigor gap rather than circularity: the theorem is not an input to its own derivation. Overall, the central theoretical claims have independent content and no circular reduction is exhibited.

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

The central claim rests on the consistency and rank assumptions, the unproven symmetry of M, and the projection property used to derive the adaptive step. No free parameters are fitted to data.

assumptions (4)

domain assumption The linear system Ax=b is consistent.
Stated in Theorem 3.2 and used throughout; without consistency the convergence target is undefined.
domain assumption rank(A) ≥ 2.
Stated in Section 2.2 and Theorem 3.2 to avoid the degenerate rank-1 case where DR reflections cancel.
ad hoc to paper The matrix M in Eq (3) is symmetric positive definite, so M^{1/2} is well-defined.
The paper proves only x^T M x > 0, which is the non-symmetric sense of positive definiteness; symmetry is not established and is false in general when row norms differ.
domain assumption The adaptive momentum sequence satisfies the projection property ⟨x_k−x0*, x_k−x_{k−1}⟩=0.
This is asserted from the optimization problem (6) and used to compute α_k and β_k in Eq (8); the base case is geometric and the recursion maintains it, but the paper does not give a formal induction.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Enhanced randomized Douglas-Rachford method: Improved probabilities and adaptive momentum." pith.science (2026). https://pith.science/paper/LGOGUPOD

@misc{pith2026250610261,
  author       = {Pith},
  title        = {Pith review of: Enhanced randomized Douglas-Rachford method: Improved probabilities and adaptive momentum},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/LGOGUPOD}},
  note         = {Machine review of arXiv:2506.10261}
}

read the original abstract

Randomized iterative methods have gained recent interest in machine learning and signal processing for solving large-scale linear systems. One such example is the randomized Douglas-Rachford (RDR) method, which updates the iterate by reflecting it through two randomly selected hyperplanes and taking a convex combination with the current point. In this work, we enhance RDR by introducing improved sampling strategies and an adaptive heavy-ball momentum scheme. Specifically, we incorporate without-replacement and volume sampling into RDR, and establish stronger convergence guarantees compared to conventional i.i.d. sampling. Furthermore, we develop an adaptive momentum mechanism that dynamically adjusts step sizes and momentum parameters based on previous iterates, and prove that the resulting method achieves linear convergence in expectation with improved convergence bounds. Numerical experiments demonstrate that the enhanced RDR method consistently outperforms the original version, providing substantial practical benefits across a range of problem settings.

Figures

Figures reproduced from arXiv: 2506.10261 by the authors.

**Figure 1.** Geometric interpretations of the Kaczmarz method and the Douglas-Rachford method. inform more effective projection directions. In this paper, we aim to develop improved sampling strategies that reduce redundancy and incorporate geometric information to accelerate convergence. Finally, we note that the RDR method was shown in [12, Theorem 3.1] to converge linearly in expectation: (2) E h kx k − x 0 ∗k 2 2 i ≤ [PITH… view at source ↗

**Figure 2.** A geometric interpretation of our design. The next iterate x k arises such that x k is the orthogonal projection of x 0 ∗ onto the affine set Πk−1 = x k−1 + Span{x k−1 − z k−1 , xk−1 − x k−2}. The following result indicates that if ˜x is not a solution to the linear system Ax = b. Then there exist {i, j} ⊆ [m] such that RHjRHi (˜x) 6= ˜x. Proposition 4.2. Suppose that rank(A) ≥ 2, and for any pair {i, j} ⊆ [m], defi… view at source ↗

**Figure 3.** Performance of RDR, mRDR, PRDR-I, PRDR-II, AmPRDR-I, and AmPRDR-II for linear systems with full rank Gaussian matrix. Figures depict the iteration and the CPU time (in seconds) vs RSE. The title of each plot indicates the values of m, n, and σ1. We fix δ = 1 and r = 100. 0 500 1000 1500 2000 Iterations 10-12 10-10 10-8 10-6 10-4 10-2 100 RSE RDR mRDR PRDR-I PRDR-II AmPRDR-I AmPRDR-II 0 0.5 1 1.5 2 2.5 Iterations 104… view at source ↗

Figures from the paper (2 more)

**Figure 4.** Figure 4: Performance of RDR, mRDR, PRDR-I, PRDR-II, AmPRDRI, and AmPRDR-II for linear systems with rank-deficient Gaussian matrix. Figures depict the iteration and the CPU time (in seconds) vs RSE. The title of each plot indicates the values of m, n, σ1, and r. We fix δ = 1 […

**Figure 5.** Figure 5: Performance of RDR, mRDR, PRDR-I, PRDR-II, AmPRDRI, and AmPRDR-II for linear systems with uniform distribution matrix. Figures depict the iteration and the CPU time (in seconds) vs RSE. The title of each plot indicates the values of m, n, and t. 5.4. Comparison to the…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

43 extracted references · 40 canonical work pages

[1]

Mon te Carlo Markov chain algorithms for sampling strongly Rayleigh distributions and determinantal point processes

Nima Anari, Shayan Oveis Gharan, and Alireza Rezaei. Mon te Carlo Markov chain algorithms for sampling strongly Rayleigh distributions and determinantal point processes. In Conference on Learning Theory, pages 103–115. PMLR, 2016

work page 2016
[2]

Recent results on Douglas- Rachford methods for combinatorial optimization problems

Francisco J Arag´ on Artacho, Jonathan M Borwein, and Matthew K Tam. Recent results on Douglas- Rachford methods for combinatorial optimization problems. J. Optim. Theory Appl. , 163(1):1–30, 2014

work page 2014
[3]

Pattern recognition and machine learning

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

work page 2006
[4]

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

work page 2018
[5]

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

work page 2021
[6]

Solving dense linear systems faster than via preconditioning

Micha/suppress l Derezi´ nski and Jiaming Yang. Solving dense linear systems faster than via preconditioning. In Proceedings of the 56th Annual ACM Symposium on Theory of Com puting, pages 1118–1129, 2024

work page 2024
[7]

On the Dougla s-Rachford splitting method and the proxi- mal point algorithm for maximal monotone operators

Jonathan Eckstein and Dimitri P Bertsekas. On the Dougla s-Rachford splitting method and the proxi- mal point algorithm for maximal monotone operators. Math. Program., 55(1):293–318, 1992

work page 1992
[8]

New variants of the POCS method using aﬃne subspaces of ﬁnite codimension with a pplications to irregular sampling

Hans Georg Feichtinger, C Cenker, M Mayer, H Steier, and T homas Strohmer. New variants of the POCS method using aﬃne subspaces of ﬁnite codimension with a pplications to irregular sampling. In Visual Communications and Image Processing’92 , volume 1818, pages 299–310. SPIE, 1992

work page

Show all 43 references

[9]

Rid geSketch: a fast sketching based solver for large scale ridge regression

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

2022
[10]

Matrix computations

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

2012
[11]

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
[12]

Randomized Doug las–Rachford methods for linear systems: Improved accuracy and eﬃciency

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

2024
[13]

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]

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 Scientiﬁc Computing , 39(5):S528–S542, 2017

2017
[15]

Algebraic reconstruction techniques can be made computation- ally eﬃcient (positron emission tomography application)

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

1993
[16]

Randomized K aczmarz in adversarial distributed setting

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

2024
[17]

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
[18]

Linear convergence of reshuﬄing Kaczmarz methods with sparse constraints

Halyun Jeong and Deanna Needell. Linear convergence of reshuﬄing Kaczmarz methods with sparse constraints. arXiv preprint arXiv:2304.10123, to appear in SIAM Journal on Scientiﬁc Computing , 2023

2023 arXiv
[19]

Angenaherte auﬂosung von systemen l inearer glei-chungen

Stefan Karczmarz. Angenaherte auﬂosung von systemen l inearer glei-chungen. Bull. Int. Acad. Pol. Sic. Let., Cl. Sci. Math. Nat. , pages 355–357, 1937

1937
[20]

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
[21]

Determinantal point proce sses for machine learning

Alex Kulesza and Ben Taskar. Determinantal point proce sses for machine learning. Foundations and Trends® in Machine Learning , 5(2–3):123–286, 2012

2012
[22]

Douglas-Rachford splittin g for nonconvex optimization with application to nonconvex feasibility problems

Guoyin Li and Ting Kei Pong. Douglas-Rachford splittin g for nonconvex optimization with application to nonconvex feasibility problems. Math. Program., 159(1):371–401, 2016. 20 LIQI GUO, RUIKE XIANG, DEREN HAN, AND JIAXIN XIE

2016
[23]

Survey: sixty years of Douglas–Rachford

Scott B Lindstrom and Brailey Sims. Survey: sixty years of Douglas–Rachford. Journal of the Australian Mathematical Society, 110(3):333–370, 2021

2021
[24]

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
[25]

The coincidence approach to stochastic p oint processes

Odile Macchi. The coincidence approach to stochastic p oint processes. Advances in Applied Probability , 7(1):83–122, 1975

1975
[26]

The mathematics of computerized tomography

Frank Natterer. The mathematics of computerized tomography . SIAM, Philadelphia, 2001

2001
[27]

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
[28]

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
[29]

Some methods of speeding up the convergence of iteration methods

Boris T Polyak. Some methods of speeding up the convergence of iteration methods. Ussr computational mathematics and mathematical physics , 4(5):1–17, 1964

1964
[30]

A randomized coor dinate descent method with volume sam- pling

Anton Rodomanov and Dmitry Kropotov. A randomized coor dinate descent method with volume sam- pling. SIAM Journal on Optimization , 30(3):1878–1904, 2020

1904
[31]

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
[32]

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
[33]

Connecting rand omized iterative methods with Krylov sub- spaces

Yonghan Sun, Deren Han, and Jiaxin Xie. Connecting rand omized iterative methods with Krylov sub- spaces. arXiv preprint arXiv:2505.20602 , 2025

2025 arXiv
[34]

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
[35]

Randomized blo ck Kaczmarz with volume sampling: Mo- mentum acceleration and eﬃcient implementation

Ruike Xiang, Jiaxin Xie, and Qiye Zhang. Randomized blo ck Kaczmarz with volume sampling: Mo- mentum acceleration and eﬃcient implementation. arXiv preprint arXiv:2503.13941 , 2025

2025 arXiv
[36]

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, to appear in SIAM Journal on Optimization , 2025

2025 arXiv
[37]

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
[38]

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
[39]

Proof of the main results 7.1

Appendix. Proof of the main results 7.1. Omitted proofs in Section 3. Proof of Proposition 3.1. We ﬁrst prove that the matrix M is positive deﬁnite. That is, for any nonzero vector x = ( x1, x2, . . . , xm)⊤ ∈ Rm, we need to show that x⊤M x > 0. Let ENHANCED RDR METHOD 21 x = ...
[40]

□ Lemma 7.2 ( [ 12], Lemma A.2)

and ( 14) into ( 12), we obtain E [ THj THi ] =I − 4 ‖A‖4 F − ‖AA⊤‖2 F A⊤( G − ¯G ) A =I − 4 ‖A‖4 F − ‖AA⊤‖2 F A⊤N A, where matrix N = G − ¯G is given by ( 3). □ Lemma 7.2 ( [ 12], Lemma A.2) . Let {xk}k≥0 and {zk}≥0 be the sequences generated by Algorithm 1. Then ‖(1 − α)xk +...
[41]

Taking the expectation over the entire history yields the de sired linear convergence result

into ( 15), we obtain E[‖xk+1 − x0 ∗‖2 2 | xk] ≤ ( 1 − 4α(1 − α) σ2 min(M 1 2 A) ‖A‖2 F ) ‖xk − x0 ∗‖2 2. Taking the expectation over the entire history yields the de sired linear convergence result. The proof under Strategy II follows analogously by replacin g the matrix M wi...
[42]

Consequently, we have uk = vk = 0, which implies zk = xk, contradicting the assumption zk ⁄= xk

that (⟨aik2 ,xk⟩−bik2 )2 ‖aik2 ‖2 2 = 0. Consequently, we have uk = vk = 0, which implies zk = xk, contradicting the assumption zk ⁄= xk. On the other hand, if ⟨aik2 ,aik1 ⟩ ‖aik1 ‖2‖aik2 ‖2 = 1 , then the vectors aik1 and aik2 are colinear, meaning the corresponding hyperplan...
[43]

□ Beihang University, Beijing, 100191, China

and ( 4), respectively. □ Beihang University, Beijing, 100191, China. Email address : glq2023@buaa.edu.cn Beihang University, Beijing, 100191, China. Email address : xiangrk@buaa.edu.cn LMIB of the Ministry of Education, School of Mathematical Sc iences, Beihang University, Be...

Pith tools

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

[1] [1]

Mon te Carlo Markov chain algorithms for sampling strongly Rayleigh distributions and determinantal point processes

Nima Anari, Shayan Oveis Gharan, and Alireza Rezaei. Mon te Carlo Markov chain algorithms for sampling strongly Rayleigh distributions and determinantal point processes. In Conference on Learning Theory, pages 103–115. PMLR, 2016

work page 2016

[2] [2]

Recent results on Douglas- Rachford methods for combinatorial optimization problems

Francisco J Arag´ on Artacho, Jonathan M Borwein, and Matthew K Tam. Recent results on Douglas- Rachford methods for combinatorial optimization problems. J. Optim. Theory Appl. , 163(1):1–30, 2014

work page 2014

[3] [3]

Pattern recognition and machine learning

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

work page 2006

[4] [4]

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

work page 2018

[5] [5]

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

work page 2021

[6] [6]

Solving dense linear systems faster than via preconditioning

Micha/suppress l Derezi´ nski and Jiaming Yang. Solving dense linear systems faster than via preconditioning. In Proceedings of the 56th Annual ACM Symposium on Theory of Com puting, pages 1118–1129, 2024

work page 2024

[7] [7]

On the Dougla s-Rachford splitting method and the proxi- mal point algorithm for maximal monotone operators

Jonathan Eckstein and Dimitri P Bertsekas. On the Dougla s-Rachford splitting method and the proxi- mal point algorithm for maximal monotone operators. Math. Program., 55(1):293–318, 1992

work page 1992

[8] [8]

New variants of the POCS method using aﬃne subspaces of ﬁnite codimension with a pplications to irregular sampling

Hans Georg Feichtinger, C Cenker, M Mayer, H Steier, and T homas Strohmer. New variants of the POCS method using aﬃne subspaces of ﬁnite codimension with a pplications to irregular sampling. In Visual Communications and Image Processing’92 , volume 1818, pages 299–310. SPIE, 1992

work page