Adaptive Row Selection Meets Asynchrony in Randomized Kaczmarz

Evan Coleman

REVIEW 2 major objections 7 minor 21 references

Adaptive Row Selection Meets Asynchrony in Randomized Kaczmarz

T0 review · 2 major / 7 minor · reviewed 2026-07-10 · grok-4.5

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

Pith's one-line read Asynchronous residual-adaptive Kaczmarz is stable only below a concurrency-dependent sampling cliff; under-relaxation and live residual reads restore usable practice.

desk verdict Solid empirical map of when residual-adaptive Kaczmarz breaks under real shared-memory asynchrony; practice-facing and carefully validated, with the usual scope limits of a measurement paper. read the letter →

arxiv 2607.08313 v1 pith:G2IRW5VD submitted 2026-07-09 cs.DC cs.NAmath.NA

Evan Coleman This is my paper · ORCID

classification cs.DCcs.NAmath.NA

keywords asynchronousiterativemethodsrandomizedKaczmarzgreedyselectionresidual-weightedsamplingshared-memoryparallelismunder-relaxationreadconsistency

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

Randomized Kaczmarz solves large sparse least-squares and tomography problems by repeatedly projecting onto one equation at a time. Adaptive rules that prefer high-residual rows speed up the sequential case, but on a shared-memory machine many lock-free workers update the residual concurrently, so the sampler often ranks a stale or interference-contaminated residual. Across 339 instrumented runs on a 96-core node with hardware-realized delays, the paper shows that stability is governed by a boundary ℓ*(T) in the plane of sampling aggressiveness versus thread count: more threads tolerate less aggressive residual bias. Below that boundary greedier sampling is strictly faster, so the practical optimum is just inside the cliff. Threshold-greedy selection, the usual accelerated rule, lies outside the boundary at high concurrency and diverges almost immediately. Under-relaxation recovers the lost region at a measurable rate cost, and live (inconsistent) residual reads never exhibited the rare scheduling-dependent divergence that snapshot reads occasionally produced, while also being cheaper. The measurements therefore give concrete defaults for shared-memory adaptive Kaczmarz and motivate a distributed two-level sampler that separates sampling staleness from iterate staleness.

What carries the argument

The power-weighted family P(i)∝|r_i|^ℓ together with the measured stability boundary ℓ*(T) and the static discriminator τχ̄ (realized delay times mean pairwise Gram-row coupling). These objects turn the interaction of residual-adaptive sampling and asynchrony into a tunable (aggressiveness, concurrency, step-size) map.

What would settle it

Rerun the same (ℓ,T) grid on a large sparse least-squares or real tomography system whose mean pairwise Gram coupling differs materially from the tested suite; if the predicted cliff location and under-relaxation rescue fail to hold, the practical tuning rules collapse.

Watch

Extended reading notes

Core claim

Stability of residual-adaptive asynchronous Kaczmarz is governed by a concurrency-dependent boundary ℓ*(T) between sampling exponent and thread count: the boundary decreases with concurrency, more aggressive residual bias is strictly beneficial only below it, and threshold-greedy selection sits outside the boundary at high thread counts and diverges almost immediately. Under-relaxation restores convergence past the cliff, and live residual reads are both safer in the observed tail and cheaper than consistent snapshots.

Load-bearing premise

The measured coupling discriminator and the observed sampling cliff, established mainly on dense gaussian and tomographic systems plus a uniform-sampling SuiteSparse slice, transfer to the broader class of large sparse least-squares and production tomography workloads without a closed-form stability theory.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

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

The useful part of this paper is the measured stability boundary ℓ*(T): under residual-weighted sampling, more threads tolerate less aggressive residual bias, and below the cliff greedier sampling is still faster. Threshold-greedy (standard GRK) sits outside that boundary at high T and blows up almost immediately. Under-relaxation recovers the cliff at a measurable rate premium, and live residual reads look safer and cheaper than consistent snapshots. That combination is new; prior adaptive and asynchronous Kaczmarz work treated the two pieces separately.

What the paper does well is the experimental craft. Delays are realized on a 96-core node, not injected. Residual maintenance is checked against recomputed b−Ax (2.4e-12 on converged runs; relative agreement 3.8e-15 at divergence flags). Sequential GRK/uniform ratios match Bai–Wu where the normalization protocols coincide. Matched seeds for read-mode pairs, three seeds per (ℓ,T) cell, and a SuiteSparse panel that ties survival to rows-per-thread and mean pairwise Gram coupling (τχ̄) make the central map credible on the problems they ran. The interference-floor story is a clean reading of the trajectories, not hand-waving.

Soft spots are real but proportionate. There is no closed-form stability criterion, so transfer of τχ̄ and the cliff beyond the gaussian/tomo family plus T=96 SuiteSparse uniform outcomes is an assumption, not a theorem. Catastrophic-divergence rates rest on 36 matched pairs (one failure); that is existence evidence, not a rate. No code or data release. The “carry directly to practice / right default” language is a bit strong for those thin tails. None of that overturns the reported measurements.

This is for people who implement parallel row-action solvers or ART-style tomography and need concrete knobs rather than folklore. It deserves a serious referee. I would engage with it, cite the boundary and the under-relaxation rescue when discussing adaptive asynchronous Kaczmarz, and push for artifacts and tempered claims on rare events.

Referee Report

2 major / 7 minor

Summary. The paper presents a systematic experimental study of residual-adaptive randomized Kaczmarz (power-weighted sampling P(i)∝|r_i|^ℓ and threshold-greedy GRK) under lock-free asynchronous shared-memory execution. Across 339 instrumented runs on a 96-core node with hardware-realized (not injected) delays, on dense Gaussian, tomographic, and SuiteSparse systems, it reports four practice-oriented findings: (i) a concurrency-dependent stability boundary ℓ*(T) in the (sampling exponent, thread count) plane below which greedier sampling is strictly faster; (ii) threshold-greedy selection diverges almost immediately at high T; (iii) under-relaxation β≤0.5 restores convergence past the cliff at a measurable asynchronous rate premium; and (iv) consistent-snapshot residual reads admit a rare scheduling-dependent early divergence that live (inconsistent) reads did not exhibit and are more expensive, so live reads are preferred. The implementation is validated by residual-maintenance checks against recomputed b−Ax and by sequential GRK/uniform iteration ratios against Bai–Wu where normalization protocols coincide.

Significance. If the reported map holds, this is the first careful measurement of the regime where adaptive row selection and asynchrony interact for Kaczmarz—precisely the setting of several recent parallel implementations that have not analyzed staleness of residual-driven sampling. The work is valuable as empirical systems science: realized delays, matched-seed read-mode pairs, residual agreement to 2.4×10^−12 (converged) and 3.8×10^−15 relative at divergence flags, and sequential reproduction of published GRK ratios where protocols coincide. The concrete engineering knobs (tune just inside ℓ*(T); under-relax to buy the cliff back; default to live reads; budget O(10) rows per thread) and the motivation for a distributed two-level sampler are useful even without a closed-form theory. Strengths to credit explicitly: residual-maintenance soundness checks, realized rather than synthetic delays, and the clear separation of iteration behavior from the O(m) sampling wall-clock bottleneck.

major comments (2)

The central empirical claim—existence of a concurrency-dependent boundary ℓ*(T) and the practical tuning rules that follow—is well supported on the gaussian/tomo family (Figs. 1–3, §V.A–C). However, the stronger claim that mean pairwise coupling χ̄ (with τ≈T−1) is the primary static discriminator that “strictly orders the stability boundary” and that rows-per-thread and τχ̄ are joint stability resources for the adaptive regime (§V.B, Conclusion, Fig. 6) rests mainly on three structured problems for adaptive ℓ and on uniform-sampling SuiteSparse outcomes at T=96 only. Fig. 6 does not map adaptive ℓ*(T) across the suite. Please either (a) add adaptive-ℓ survival data on a representative subset of the SuiteSparse matrices, or (b) clearly delimit in the abstract, §V.B, and Conclusion that the τχ̄ ordering and the “tune just inside the cliff” rule are established for the gaussian/tomo couplin
§V.C and Fig. 3: the claim that under-relaxation buys back the cliff “at a predictable cost” with an asynchronous interference premium of “roughly two” (abstract; also “1.7–2.3×” in the text) is supported only on the cliff cells that diverge at β=1 (21 rescue runs). The synchronous factor 1/[β(2−β)] is a useful baseline, but calling the premium predictable for general use requires either more cells (including non-cliff and SuiteSparse) or a softer statement that the premium was observed in the range 1.7–2.3× on the tested cliff configurations. As written, “predictable” and the abstract’s safety-knob language slightly overstate the breadth of the measurement.

minor comments (7)

Abstract and §I: “Four findings carry directly to practice” is strong for an empirical map without a closed-form criterion. Soften to “suggest the following practical defaults on the tested regimes” or similar once the scope delimitation above is in place.
Table II / §V.D: the Clopper–Pearson intervals correctly overlap; the text already frames this as existence and asymmetry, not a rate difference. Consider moving the table to a short appendix or footnote so the main narrative does not invite over-reading of n=36.
Fig. 4 and §V.E: the 4.4× wall-clock speedup on 96 threads (O(m) sampling bottleneck) is an important practical caveat. Mention it earlier when stating that asynchrony is “cheap in iteration terms,” so readers do not infer wall-clock scalability from the flat sweep counts alone.
Algorithm 1, line 5: the conditional “if inconsistent then re-read r_i else snapshot r_i” is clear, but a one-sentence note that GRK’s threshold and sampling passes may see different live residuals (already in §III.C) would help readers who jump to the algorithm box.
Related work: RGDBEK [10] is cited as performance engineering without staleness-aware analysis; a sentence on whether any of [8], [9], [10] use residual-weighted or greedy selection under lock-free updates would sharpen the novelty claim.
Notation: ℓ for the power exponent and ℓ*(T) for the boundary is fine, but ν_2(r) (IPR) is introduced in §III.A and then used heavily in §V.A without restating the formula near Fig. 1; a brief reminder in the caption would help.
Typos / polish: “Index Terms” line is fine; check consistency of “tomo-4x” vs “tomo (point)” labeling in Table I and the point-phantom paragraph; “de-censored to 400 sweeps” (§V.D) is slightly informal for the main text.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: empirical stability map from measured converge/diverge outcomes, not a derivation that reduces to its inputs.

full rationale

This is a shared-memory measurement study of residual-adaptive asynchronous Kaczmarz (339 runs, realized delays). The central object ℓ*(T) is the observed converge/diverge boundary in the (ℓ,T) plane (Fig. 2, §V.A–B); it is not derived from a fitted constant that is then re-presented as a prediction. Outcomes (sweeps to tolerance, residual blow-up, wall-clock) are external observables. Implementation soundness is checked independently: maintained residual vs recomputed b−Ax (≤2.4e−12 converged; ≤3.8e−15 relative at divergence flag), and sequential GRK/uniform ratios reproduce Bai–Wu [2] where normalization protocols coincide. The discriminator τχ̄ is proposed from static structure (Table I) and then tested on SuiteSparse uniform outcomes (Fig. 6)—hypothesis then independent check, not fit-as-prediction. Under-relaxation cost is reported as measured excess over the known synchronous 1/[β(2−β)] factor, not a circular forecast. Self-citation of the companion Jacobi paper [11] is used only for contrast (read-consistency axis vs coupling-aggressiveness axis), not as a uniqueness theorem or definitional premise for the Kaczmarz boundary. No self-definitional loop, no fitted input renamed as prediction, no load-bearing self-citation chain. Score 0 is the honest finding.

Assumptions & free parameters 3 free parameters · 5 assumptions · 2 invented entities

The paper is primarily empirical. Load-bearing background is standard Kaczmarz/asynchrony theory and experimental design choices (consistent systems, precomputed Gram residual maintenance, divergence thresholds). The named stability boundary ℓ*(T) and the interference-floor interpretation are observational constructs, not free physical entities. No large fitted theory constants drive the central claim.

free parameters (3)

divergence residual threshold = 1e8
Runs are flagged divergent when ||r||/||b|| > 10^8 (§IV). This cutoff defines which cells count as unstable and thus shapes the reported ℓ*(T) map; it is a design choice, not derived.
asynchronous interference premium factor = ~1.7–2.3×
Observed under-relaxation penalty is reported as ~1.7–2.3× the synchronous 1/[β(2−β)] prediction (§V.C). The 'roughly two' premium is a measured summary used in the practice claim, not a first-principles constant.
rows-per-thread survival floor = ~1 (hard floor); O(10) recommended
Fig. 6 / conclusion suggest budgeting at least O(10) rows per thread and note nothing survives below roughly one row per thread at T=96 uniform sampling. These thresholds are read off the SuiteSparse scatter, not derived.

assumptions (5)

domain assumption Rows are normalized to unit Euclidean norm and systems are constructed consistent via b = A x* so residual and solution error are both available.
§III.A and §IV; standard for Steinerberger/AsyRK-style studies but excludes inconsistent least-squares behavior that many applications face.
domain assumption Workers maintain the residual exactly via precomputed sparse Gram-row updates r ← r − λ Q_i,: rather than recomputing b−Ax each step.
§III.B; enables the measurement study but assumes Q is available and that this maintenance model matches practical residual handling.
domain assumption Lock-free atomic updates with realized dispatch-to-commit delays on the target shared-memory node are the right model of asynchrony (no synthetic delay injection).
§IV; delays are hardware/schedule properties, so conclusions are tied to that execution model.
standard math Power-weighted sampling P(i) ∝ |r_i|^ℓ interpolates from uniform (ℓ→0) to Motzkin/greedy (ℓ→∞), and threshold-greedy GRK is the standard accelerated rule to stress-test.
§I–III citing Steinerberger, Bai–Wu, Motzkin line; defines the aggressiveness axis of the study.
ad hoc to paper Mean pairwise coupling χ̄ = E|Q_ij| (with τ ≈ T−1) is the primary static discriminator of the stability boundary among the tested structure statistics.
§V.B and Fig. 6; ordered the built-in problems and SuiteSparse outcomes better than spectral proxies, but is an empirical selection among candidates rather than a proved Lyapunov criterion.

invented entities (2)

stability boundary ℓ*(T) independent evidence
purpose: Names the observed frontier in the (sampling exponent, thread count) plane separating convergence from divergence under residual-adaptive asynchronous Kaczmarz.
Central organizing construct of the paper (§I, §V.B, Fig. 2). It is measured, not derived from a closed-form theorem; independent evidence is the multi-seed experimental map itself.
asynchronous interference floor / neighborhood interference floor
purpose: Interpretive mechanism: once residual magnitude reaches the scale of Θ(T) in-flight update perturbations, residual-weighted sampling ranks interference rather than signal and can enter a feedback loop.
Introduced in §V.A to explain mid-run divergence after initial residual drop (e.g., ℓ=2 gaussian). Plausible and trajectory-consistent, but not independently measured as a separate physical quantity outside these runs.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Adaptive Row Selection Meets Asynchrony in Randomized Kaczmarz." pith.science (2026). https://pith.science/paper/G2IRW5VD

@misc{pith2026260708313,
  author       = {Pith},
  title        = {Pith review of: Adaptive Row Selection Meets Asynchrony in Randomized Kaczmarz},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/G2IRW5VD}},
  note         = {Machine review of arXiv:2607.08313}
}

abstract

Randomized Kaczmarz is a natural fit for large sparse least-squares and tomographic reconstruction, and adaptive row selection can reduce iteration counts. However, deploying adaptive selection on a shared-memory machine means sampling from a residual that lock-free workers are concurrently modifying, often using stale data. We present the first systematic study of this regime: residual-weighted and greedy Kaczmarz under asynchronous execution, measured across 339 runs on a 96-core node with realized (not injected) delays. Four findings carry directly to practice. (i) Stability is governed by a boundary $\ell^*(T)$ between sampling aggressiveness and thread count; below it, more aggressive sampling is strictly better, so one should tune to just inside the cliff. (ii) Threshold-greedy selection (the standard accelerated rule) is unstable at high thread counts, diverging almost immediately. (iii) Under-relaxation buys back the cliff at a predictable cost, giving a usable safety knob. (iv) Consistent-snapshot reads admit a rare, scheduling-dependent divergence that live (inconsistent) reads never exhibited and that is also cheaper, making inconsistent reads the right default. We validate the implementation against published sequential results and outline the distributed two-level sampler these measurements motivate.

Figures

Figures reproduced from arXiv: 2607.08313 by the authors.

**Figure 2.** Stability boundary ℓ ∗ (T) over the (sampling exponent, thread count) plane; three seeds per cell, green annotated with median sweeps to tolerance (or relative residual at the 200-sweep cap). The boundary decreases with concurrency, and below it the synchronous ordering survives (greedier is strictly faster) so tuning is a race to a concurrency-dependent cliff. The mixed cell (two converge, one diverges) shows the b… view at source ↗

**Figure 3.** Sweeps to tolerance versus relaxation parameter [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗

Figures from the paper (3 more)

**Figure 4.** Figure 4: Scaling on the headline tomo instance. Wall-clock speedup saturates at [PITH_FULL_IMAGE:figures/full_fig_p010_4.png]

**Figure 5.** Figure 5: Six same-configuration consistent-reads runs, tomo, [PITH_FULL_IMAGE:figures/full_fig_p012_5.png]

**Figure 6.** Figure 6: Asynchronous survival predicted from two static quantities (uniform sampling, [PITH_FULL_IMAGE:figures/full_fig_p013_6.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

21 extracted references · 21 canonical work pages

[1]

A randomized Kaczmarz algorithm with exponential convergence,

T. Strohmer and R. Vershynin, “A randomized Kaczmarz algorithm with exponential convergence,”Journal of Fourier Analysis and Applications, vol. 15, no. 2, pp. 262–278, 2009

work page 2009
[2]

On greedy randomized Kaczmarz method for solving large sparse linear systems,

Z.-Z. Bai and W.-T. Wu, “On greedy randomized Kaczmarz method for solving large sparse linear systems,”SIAM Journal on Scientific Computing, vol. 40, no. 1, pp. A592–A606, 2018

work page 2018
[3]

A weighted randomized Kaczmarz method for solving linear systems,

S. Steinerberger, “A weighted randomized Kaczmarz method for solving linear systems,”Mathematics of Computation, vol. 90, no. 332, pp. 2815–2826, 2021

work page 2021
[4]

Greed works: An improved analysis of sampling Kaczmarz–Motzkin,

J. Haddock and A. Ma, “Greed works: An improved analysis of sampling Kaczmarz–Motzkin,”SIAM Journal on Mathematics of Data Science, vol. 3, no. 1, pp. 342–368, 2021

work page 2021
[5]

On adaptive sketch-and-project for solving linear systems,

R. M. Gower, D. Molitor, J. Moorman, and D. Needell, “On adaptive sketch-and-project for solving linear systems,”SIAM Journal on Matrix Analysis and Applications, vol. 42, no. 2, pp. 954–989, 2021

work page 2021
[6]

Revisiting Asynchronous Linear Solvers: Provable Convergence Rate Through Randomization

H. Avron, A. Druinsky, and A. Gupta, “Revisiting asynchronous linear solvers: Provable convergence rate through randomization,”Journal of the ACM, vol. 62, no. 6, pp. 51:1–51:27, 2015, preprint: arXiv:1304.6475

work page Pith review arXiv 2015
[7]

An Asynchronous Parallel Randomized Kaczmarz Algorithm

J. Liu, S. J. Wright, and S. Sridhar, “An asynchronous parallel randomized Kaczmarz algorithm,”arXiv preprint arXiv:1401.4780, 2014

work page Pith review arXiv 2014
[8]

PRKP: A parallel randomized iterative algorithm for solving linear systems,

J. Wang, M. Tian, Y . Wang, G. He, and T. Liu, “PRKP: A parallel randomized iterative algorithm for solving linear systems,” in2022 IEEE 24th Int Conf on High Performance Computing & Communications; 8th Int Conf on Data Science & Systems; 20th Int Conf on Smart City; 8th Int Conf on Dependability in Sensor, Cloud & Big Data Systems & Application (HPCC/DSS...

work page 2022

Show all 21 references

[9]

A distributed memory parallel randomized Kaczmarz for sparse system of equations,

E. S. Bölükba¸ sı, F. ¸ S. Torun, and M. Manguo˘glu, “A distributed memory parallel randomized Kaczmarz for sparse system of equations,”Concurrency and Computation: Practice and Experience, vol. 36, no. 25, p. e8274, 2024. 15

2024
[10]

RGDBEK: Randomized greedy double block extended Kaczmarz algorithm with hybrid parallel implementation and applications,

A. Panchal and R. Behera, “RGDBEK: Randomized greedy double block extended Kaczmarz algorithm with hybrid parallel implementation and applications,”arXiv preprint arXiv:2509.19267, 2025

2025
[11]

Residual-weighted randomized Jacobi: Sharpened bounds via residual concentration and asynchronous extension,

E. Coleman, “Residual-weighted randomized Jacobi: Sharpened bounds via residual concentration and asynchronous extension,”arXiv preprint arXiv:2606.01232, 2026

2026 arXiv
[12]

Algebraic reconstruction techniques (ART) for three-dimensional electron microscopy and X-ray photography,

R. Gordon, R. Bender, and G. T. Herman, “Algebraic reconstruction techniques (ART) for three-dimensional electron microscopy and X-ray photography,”Journal of Theoretical Biology, vol. 29, no. 3, pp. 471–481, 1970

1970
[13]

Randomized methods for linear constraints: convergence rates and conditioning,

D. Leventhal and A. S. Lewis, “Randomized methods for linear constraints: convergence rates and conditioning,” Mathematics of Operations Research, vol. 35, no. 3, pp. 641–654, 2010

2010
[14]

A weighted randomized sparse Kaczmarz method for solving linear systems,

L. Zhang, Z. Yuan, H. Wang, and H. Zhang, “A weighted randomized sparse Kaczmarz method for solving linear systems,” Computational and Applied Mathematics, vol. 41, p. 383, 2022

2022
[15]

Convergence rates for greedy Kaczmarz algorithms, and faster randomized Kaczmarz rules using the orthogonality graph,

J. Nutini, B. Sepehry, I. Laradji, M. Schmidt, H. Koepke, and A. Virani, “Convergence rates for greedy Kaczmarz algorithms, and faster randomized Kaczmarz rules using the orthogonality graph,” inProceedings of the 32nd Conference on Uncertainty in Artificial Intelligence (UAI), 2016

2016
[16]

On Motzkin’s method for inconsistent linear systems,

J. Haddock and D. Needell, “On Motzkin’s method for inconsistent linear systems,”BIT Numerical Mathematics, vol. 59, no. 2, pp. 387–401, 2019

2019
[17]

Randomized Kaczmarz with averaging,

J. D. Moorman, T. K. Tu, D. Molitor, and D. Needell, “Randomized Kaczmarz with averaging,”BIT Numerical Mathematics, vol. 61, no. 1, pp. 337–359, 2021

2021
[18]

Randomized block Kaczmarz method with projection for solving least squares,

D. Needell, R. Zhao, and A. Zouzias, “Randomized block Kaczmarz method with projection for solving least squares,” Linear Algebra and its Applications, vol. 484, pp. 322–343, 2015

2015
[19]

Chaotic relaxation,

D. Chazan and W. Miranker, “Chaotic relaxation,”Linear Algebra and its Applications, vol. 2, no. 2, pp. 199–222, 1969

1969
[20]

HOGWILD!: A lock-free approach to parallelizing stochastic gradient descent,

B. Recht, C. Re, S. Wright, and F. Niu, “HOGWILD!: A lock-free approach to parallelizing stochastic gradient descent,” Advances in Neural Information Processing Systems, vol. 24, 2011

2011
[21]

Component-averaged row projections: a robust, block-parallel scheme for sparse linear systems,

D. Gordon and R. Gordon, “Component-averaged row projections: a robust, block-parallel scheme for sparse linear systems,”SIAM Journal on Scientific Computing, vol. 27, no. 3, pp. 1092–1117, 2005

2005

Pith tools

Reviewed July 10, 2026 · model on record in the stance chip above.

[1] [1]

A randomized Kaczmarz algorithm with exponential convergence,

T. Strohmer and R. Vershynin, “A randomized Kaczmarz algorithm with exponential convergence,”Journal of Fourier Analysis and Applications, vol. 15, no. 2, pp. 262–278, 2009

work page 2009

[2] [2]

On greedy randomized Kaczmarz method for solving large sparse linear systems,

Z.-Z. Bai and W.-T. Wu, “On greedy randomized Kaczmarz method for solving large sparse linear systems,”SIAM Journal on Scientific Computing, vol. 40, no. 1, pp. A592–A606, 2018

work page 2018

[3] [3]

A weighted randomized Kaczmarz method for solving linear systems,

S. Steinerberger, “A weighted randomized Kaczmarz method for solving linear systems,”Mathematics of Computation, vol. 90, no. 332, pp. 2815–2826, 2021

work page 2021

[4] [4]

Greed works: An improved analysis of sampling Kaczmarz–Motzkin,

J. Haddock and A. Ma, “Greed works: An improved analysis of sampling Kaczmarz–Motzkin,”SIAM Journal on Mathematics of Data Science, vol. 3, no. 1, pp. 342–368, 2021

work page 2021

[5] [5]

On adaptive sketch-and-project for solving linear systems,

R. M. Gower, D. Molitor, J. Moorman, and D. Needell, “On adaptive sketch-and-project for solving linear systems,”SIAM Journal on Matrix Analysis and Applications, vol. 42, no. 2, pp. 954–989, 2021

work page 2021

[6] [6]

Revisiting Asynchronous Linear Solvers: Provable Convergence Rate Through Randomization

H. Avron, A. Druinsky, and A. Gupta, “Revisiting asynchronous linear solvers: Provable convergence rate through randomization,”Journal of the ACM, vol. 62, no. 6, pp. 51:1–51:27, 2015, preprint: arXiv:1304.6475

work page Pith review arXiv 2015

[7] [7]

An Asynchronous Parallel Randomized Kaczmarz Algorithm

J. Liu, S. J. Wright, and S. Sridhar, “An asynchronous parallel randomized Kaczmarz algorithm,”arXiv preprint arXiv:1401.4780, 2014

work page Pith review arXiv 2014

[8] [8]

PRKP: A parallel randomized iterative algorithm for solving linear systems,

J. Wang, M. Tian, Y . Wang, G. He, and T. Liu, “PRKP: A parallel randomized iterative algorithm for solving linear systems,” in2022 IEEE 24th Int Conf on High Performance Computing & Communications; 8th Int Conf on Data Science & Systems; 20th Int Conf on Smart City; 8th Int Conf on Dependability in Sensor, Cloud & Big Data Systems & Application (HPCC/DSS...

work page 2022