Accelerated Exact Recovery from Noisy Data via Averaging and Noise-Aware Adaptive Bregman-Kaczmarz

Abakar A. Mahamat; Idriss Tondji; Lionel Tondji

REVIEW 3 major objections 5 minor 32 references

Accelerated Exact Recovery from Noisy Data via Averaging and Noise-Aware Adaptive Bregman-Kaczmarz

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

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

Pith's one-line read The paper proves that an averaged, noise-weighted, adaptively stepped Bregman-Kaczmarz method recovers the exact noise-free solution of a consistent linear system even when every query carries fresh zero-mean noise, and that its guaranteed

desk verdict The averaging-plus-adaptive-step idea is real and the T-matrix analysis is clean, but Theorem 2.1 is false as stated because it omits the standard initialization x*_0 in R(A^T). read the letter →

arxiv 2607.16003 v1 pith:O6XBKVN2 submitted 2026-07-17 math.NA cs.NAmath.OC

Lionel Tondji , Abakar A. Mahamat , Idriss Tondji This is my paper · ORCID

classification math.NAcs.NAmath.OC MSC 65F1015A2965F20

keywords randomizedBregman-Kaczmarzadaptivestepsizeaveraginginverseproblemsblockmethodsheteroscedasticnoiseexactrecoverystablerank

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

The paper claims that a block version of the adaptive Bregman-Kaczmarz method can both provably accelerate with batch size and still recover the exact noise-free solution of a consistent linear system, even though every measurement it queries carries freshly drawn zero-mean noise. The key move is to average the block updates rather than sum them; this collapses the analysis onto a single positive semidefinite matrix T whose largest eigenvalue decreases monotonically with the batch size. The paper further introduces a noise-aware weighting and sampling rule that provably lowers the rate constant below uniform weighting whenever row noise is not proportional to row norms—a condition the authors argue is 'essentially never' met in practice. If true, this would be the first averaged adaptive Bregman-Kaczmarz method with proven exact recovery and batch-size acceleration, offering a practical way to exploit parallel hardware and heterogeneous noise information simultaneously.

What carries the argument

The central object is the positive semidefinite matrix T = (1/(2τ))W + (α/(2||A||_F^2))(1 − 1/τ)AA^T, which combines the weight matrix W, the Gram matrix AA^T, the batch size τ, and the relaxation α. Its spectral radius σ_max(T) sets the per-step contraction, and because the update is an average rather than a sum, σ_max(T) decreases with τ, making larger batches provably faster. The adaptive step η_k = αγβ_k / (1 + 2αγσ_max(T)β_k) with β_{k+1} = β_k(1 − αγη_k/2) is the second load-bearing mechanism: the shrinking tail of β_k (and hence η_k ~ 1/k) averages out the fresh noise and drives the error exactly to zero. The coupling (3), p_i w_i / ||a_i||^2 = α/||A||_F^2, ties sampling probabilities

What would settle it

Run AABK on a fixed random Gaussian system (m=2000, n=100) with known per-row variances, compare the expected error at a fixed iteration for τ=1 and τ=20, and check that the τ=20 curve continues to decrease to zero at the rate predicted by the stable rank factor; a plateau above the noise floor, or a slowdown inconsistent with the predicted factor, would contradict the bound (8).

Watch

Extended reading notes

Core claim

Under the independent-noise model (each query of row j returns b_j plus a fresh zero-mean error of known variance σ_j^2), with the coupling p_i w_i / ||a_i||^2 = α/||A||_F^2 and the error-bound Assumption 3.2, Theorem 2.1 states that the iterates of Algorithm 1 satisfy E||x_k − x̂||^2 ≤ (2 Tr(PW^2ΣD^{-2})/τ) β_k, where β_k is deterministic and decreases to zero; hence the iterates converge in expectation to the exact noise-free solution. The proof reduces to the PSD matrix T = (1/2τ)W + (α/(2||A||_F^2))(1 − 1/τ)AA^T: its largest eigenvalue controls the contraction factor, and the 1/τ factor from averaging is what makes σ_max(T) shrink with τ. Proposition 2.2 shows the guaranteed rate improve

Load-bearing premise

The entire exact-recovery guarantee rests on the independent-noise model: every query of a row returns a fresh, zero-mean error with known strictly positive variance, because it is the shrinking step size averaging over these fresh errors that drives the iterates to the exact solution.

Editorial extensions

If this is right

If Theorem 2.1 holds, exact recovery from fresh noisy measurements requires no regularization beyond the strongly convex penalty f; the noise is averaged away by the adaptive step, not suppressed by a noise ball.
The monotonicity result means doubling the batch size strictly improves the guaranteed contraction (for uniform weights), so parallel hardware that can evaluate more rows per step is directly converted into a provably faster method.
The noise-aware weighting gives a principled way to prioritize measurements: sample rows in proportion to σ_i ||a_i|| and weight them inversely to their noise—a concrete recipe for heteroskedastic sensor noise.
The step-size analysis (Corollary 2.4) shows the method is self-tuning between regimes: a constant over-relaxed step early (even >1, unlike standard ABK) and a 1/k Robbins-Monro tail later; users do not need to switch step rules.
The heuristic estimation of γ and β_0 from one auxiliary run means the method can be deployed without access to the true solution, needing only the two phase-window indices N_0 and N_1.

Reading between the lines

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

Because the variance reduction enters through the 1/τ factor in T, the averaging trick is not specific to Bregman-Kaczmarz; any row-action or stochastic-gradient method whose update is a sum could likely be averaged to obtain a similar batch-size monotonicity, as long as fresh noise is available.
The optimal weighting requires knowing each σ_i; an untested but natural extension is to estimate variances online by querying each row repeatedly at startup, then feed the estimates into the weighting rule.
The paper proves expectation bounds; the natural next step (which the authors note) is high-probability concentration, which would be needed for single-run guarantees in real-time imaging or control.
The observation that the averaged step permits η_k > 1 suggests an over-relaxation principle for noisy stochastic iterations generally; early over-relaxation plus tail decay might accelerate other adaptive stochastic algorithms.

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

Read this one. The core idea — averaging the block updates and combining with the adaptive Bregman–Kaczmarz step — is genuinely new, and the reduction to a single PSD matrix T is elegant. But the main theorem is false as stated: it omits the standard initialization condition x*_0 ∈ R(A^T). Concrete counterexample: A = [1, 0], b = 0, f(x) = ½‖x‖², x*_0 = (0,1). The single row has zero residual for every iterate, so d_k = 0 forever, x_k stays at (0,1), while (8) predicts convergence to 0. The induction in Lemma 4.2 applies Assumption 3.2 at x_k with x*_k, which requires x*_k ∈ R(A^T); the update preserves that only if x*_0 is in R(A^T). So the theorem needs one extra hypothesis. That is a small fix — x*_0 = 0 works and is what the experiments actually use — but it is load-bearing and must be stated.

What is genuinely good: the monotone-in-τ guarantee with stable-rank gain via the averaged T matrix, the noise-aware weights p_i ∝ σ_i‖a_i‖ with the Cauchy–Schwarz optimality argument, and the clean step-size asymptotics (Lambert-W, 1/k tail). The related-work table correctly identifies this cell as empty; [27] explicitly left block-size acceleration open. Lemma 4.3 is deferred to [24], which is acceptable if that reference is solid. The self-citations are legitimate here: the new content is derived from first-principles bounds, not fitted.

Other soft spots, in decreasing order. (1) The optimal weights give p_i = 0 for a noiseless row (σ_i = 0), so that row is never sampled; the paper neither assumes σ_i > 0 nor discusses the edge case. (2) The synthetic headline comparisons use oracle β_0 (ground truth) for ABK and AABK, which flatters them; the CT heuristic runs are more honest. (3) No error bars or released code.

Verdict: this deserves a serious referee. Fix the missing hypothesis, clean up the experimental protocol, and separate the exact-β_0 theorem from the heuristic estimators, and it becomes a solid contribution. I'd take it to reading group as-is — the flaw is instructive.

Referee Report

3 major / 5 minor

Summary. The paper introduces the Adaptive Averaged Bregman-Kaczmarz (AABK) method for linear inverse problems in which every queried measurement is corrupted by fresh, independent, zero-mean noise. The method averages a batch of weighted Bregman-Kaczmarz updates and uses an adaptive step size. The main result (Theorem 2.1) gives a bound on the expected squared error, E||x_k - x_hat||^2 <= (2 Tr(PW^2 Sigma D^{-2})/tau) beta_k, with beta_k -> 0, implying exact recovery of the minimum-f solution. The authors prove that the guaranteed contraction improves monotonically with batch size tau, propose noise-aware weights that minimize the noise prefactor, and analyze the step-size asymptotics. Numerical experiments on synthetic data and CT reconstruction support the qualitative claims.

Significance. If the main theorem is correct, the paper resolves a genuine open question: whether block/batch versions of adaptive Bregman-Kaczmarz can be proven to accelerate with batch size. The key reduction to a single positive-semidefinite matrix T is elegant, and the combination of averaging, adaptive stepping, and noise-aware weighting is a meaningful advance over the authors' earlier ABK and RSKA methods. The paper is also carefully written, with detailed appendices for the one-step bound, spectral estimates, the step-size recursion, and the optimal-weight derivation. The numerical experiments are relevant and support the main qualitative predictions. However, the central theorem as stated has a missing initialization hypothesis that makes it false, and the superiority claim for the noise-aware weights is only established for the prefactor, not for the full convergence bound. These issues are fixable but currently compromise the paper's main claims.

major comments (3)

[Theorem 2.1, Lemma 4.2, Assumption 3.2] The main theorem is false as stated because it omits the initialization condition x*_0 in R(A^T). Lemma 4.2 applies Assumption 3.2 at x = x_k, x* = x*_k, which requires x*_k in ∂f(x_k) ∩ R(A^T). Since d_k in R(A^T), this membership is preserved only if x*_0 in R(A^T). Without it, the null(A) component of x*_0 is never updated. Concrete counterexample: A = [1,0], b = 0, f(x) = 0.5||x||^2, x*_0 = (0,1), any σ_1>0. The single row has zero residual at every iterate, so d_k = 0 and x_k = (0,1) for all k, while (8) predicts convergence to 0. Add the explicit hypothesis x*_0 in R(A^T) (e.g., x*_0 = 0) to Theorem 2.1 and Algorithm 1.
[Corollary 2.3, §4.5, Eq. (3)] The optimal noise-aware weighting p_i ∝ σ_i||a_i||, w_i ∝ ||a_i||/σ_i is derived by minimizing Σ σ_i^2||a_i||^2/p_i over p_i ≥ 0. If σ_i = 0 for a noiseless row, the formal minimizer sets p_i = 0, which violates the standing coupling (3) because the right-hand side α/||A||_F^2 is positive for every i. The elimination step w_i = α||a_i||^2/(p_i||A||_F^2) then also becomes undefined. Moreover, Theorem 2.1 divides by Tr(PW^2ΣD^{-2}), so this quantity must be positive. Please state explicitly that σ_i > 0 for all i, or introduce an epsilon-floor in the sampling distribution and adjust the optimality claim.
[Corollary 2.3 / Abstract, Eq. (8)] The claimed strict superiority of the noise-aware weights over uniform weighting is established only for the prefactor C_noise = Tr(PW^2ΣD^{-2}), not for the full expected-error bound (8). The weights W also enter the matrix T in (6) and hence the step sequence and the decay factor β_k. The optimal weights can make σ_max(T) (or the certified bound U(τ)) much larger than in the uniform case W = αI, slowing the decay of β_k. For example, with A = [1;1], τ = 1 and σ = (1, ε), the optimal weights give σ_max(W) ≈ 1/(2ε), whereas uniform gives σ_max(W) = α. Thus a smaller prefactor can be offset by a slower rate; the paper's abstract and contribution list state that the weighting is 'strictly better' without qualifying this. Please either prove a comparison for the full bound or explicitly restrict the claim to the noise prefactor and asymptotic tail.

minor comments (5)

[Table 2] The SSIM/PSNR row contains missing separators: '0.86120.9409' and '24.547931.6334' should be separate values with proper column separation.
[Figure 3] The vertical axis label 'xK' should be 'x_k' (or |x_k - x_hat|/|x_hat|).
[Lemma 4.3] The main text says 'The detailed proof of this lemma can be found in [24]', but Appendix C contains a full proof. Cite the appendix instead, or remove the reference to [24].
[§2.6, Eqs. (9)-(10)] The heuristic estimators replace x_hat by x_N without stating the approximation clearly. Please clarify that the formulas are computed with Bregman distances to x_N and are therefore only valid when x_N is sufficiently close to x_hat.
[Algorithm 1] The algorithm input should include the initialization condition x*_0 ∈ R(A^T) (or x*_0 = 0) in view of the missing hypothesis in Theorem 2.1.

Circularity Check

0 steps flagged · score 2.0 of 10

No significant circularity: the main convergence, batch-acceleration, and noise-aware weighting results are derived from first-principles bounds in this paper; self-citations are contextual, not load-bearing.

full rationale

Theorem 2.1's proof is self-contained: Lemma 4.2 derives the expected descent from the update (4)-(5) and coupling (3), producing the psd matrix T in (6) through the explicit expectation identities of Appendix B. The adaptive step (7) is obtained by minimizing the unrolled one-step bound D_k over eta_k, not by fitting to the conclusion; the sequence beta_k is an auxiliary Lyapunov-type bound whose initial value is the initial Bregman distance to xhat. That beta_0 depends on xhat is a standard initial-condition constant, not a concealed use of the theorem's target. Proposition 2.2 follows arithmetically from the spectral formula for T in Lemma 4.3, which is proved in Appendix C; the pointer to [24] is not the proof. Corollary 2.3 is a direct convex optimization/Cauchy-Schwarz computation. Corollary 2.4 solves the deterministic beta recursion via the Lambert-W function. The self-citations to ABK [27] and RSKA [24] supply the baselines, the block-ABK motivation, and the heuristic-estimation template, but they are not invoked to establish the new convergence, monotone-acceleration, or noise-aware-weighting claims. Assumption 3.2 is stated as an explicit hypothesis, and its validity for the elastic-net f is attributed primarily to [19], which has no author overlap with this paper; [20] is secondary. Section 2.6's heuristic estimation is explicitly a practical fitting device, and Section 6 admits the dependence on user-chosen windows N_0, N_1; this is a practical identifiability limitation, not circular reasoning. The missing hypothesis x*_0 in R(A^T) noted by a skeptical reader is a correctness/gap issue, not a circularity: nothing in the text defines the theorem's conclusion in terms of the step-size parameters or vice versa. No equation in the paper reduces to its own input by construction, so the appropriate finding is no significant circularity.

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

No new physical entities are introduced. The free parameters above are the ones the algorithm actually needs to run; gamma and beta_0 are the most consequential because the theorem's convergence guarantee assumes exact beta_0, while practice must estimate it. The paper is honest about the heuristics, but the ledger shows the method is not parameter-free.

free parameters (5)

gamma (error-bound constant theta/||A||_F^2) = Grid-selected in synthetic experiments (e.g., 0.01); guessed as 1e-4 or heuristically estimated in CT
The step size (7) depends on gamma, which is not known a priori; Assumption 3.2 only asserts existence of theta. Experiments choose gamma by tuning.
beta_0 (initial auxiliary sequence) = Exact formula tau D0/C; synthetic uses ground truth; CT heuristic values up to 1.8e10
The theoretical convergence bound requires beta_0 equal to tau D^{x*_0}_f(x_0, x_hat)/Tr(PW^2 Sigma D^{-2}), which contains the unknown solution distance. The paper estimates it heuristically in Section 2.6.
alpha (coupling relaxation parameter) = 1 in all experiments
Alpha appears in the coupling (3), in T, and in the step rule. It is chosen by hand rather than determined by the problem.
lambda (sparsity parameter in f) = 0.5 synthetic, 30 CT
The regularizer f(x)=lambda||x||_1 + 0.5||x||_2^2 requires choosing lambda. It is a user-set modeling parameter, not fitted by the theory.
N_0, N_1 (heuristic window indices) = N_0=10000, N_1=25000 in CT
The estimators (9)-(10) require choosing indices delimiting the decay and plateau phases. The paper states these play a significant role.

assumptions (5)

domain assumption Assumption 3.2 error bound: ||Ax-b||^2 >= theta(x_hat) D_f^{x*}(x, x_hat) for iterates with ∂f(x) ∩ R(A^T) nonempty
Invoked in Lemma 4.2 to convert the residual into Bregman distance. It is standard for the elastic-net f via [19, Lemma 3.1], but not proven for all f in this paper.
ad hoc to paper Coupling p_i w_i / ||a_i||^2 = alpha / ||A||_F^2 for all i (Eq. 3)
Imposed so the PWD^{-2} factors collapse to a scalar identity. The authors admit the fully optimal (p, w) pair may lie outside this coupling.
domain assumption Independent fresh zero-mean noise with known variances sigma_i^2 > 0 (Eq. 2)
Exact recovery depends on noise being averaged out by the shrinking step. The optimal weights are undefined at sigma_i=0 and give p_i=0 to noiseless rows, an unhandled edge case.
standard math f is 1-strongly convex, finite everywhere, with conjugate gradient Lipschitz; Bregman distance identities
Used throughout Lemmas 4.1-4.2 and the proof of Theorem 2.1. Any mu-strongly convex f can be rescaled to mu=1.
domain assumption Sampling is i.i.d. with replacement, and repeated draws of the same row get independent fresh noise
Used in the second-moment identity (18) and the noise-variance computation in Appendix B.5. Sampling without replacement would change the variance terms.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Accelerated Exact Recovery from Noisy Data via Averaging and Noise-Aware Adaptive Bregman-Kaczmarz." pith.science (2026). https://pith.science/paper/O6XBKVN2

@misc{pith2026260716003,
  author       = {Pith},
  title        = {Pith review of: Accelerated Exact Recovery from Noisy Data via Averaging and Noise-Aware Adaptive Bregman-Kaczmarz},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/O6XBKVN2}},
  note         = {Machine review of arXiv:2607.16003}
}

read the original abstract

The adaptive Bregman-Kaczmarz method recovers the exact, noise-free solution of a linear inverse problem even when every measurement it queries is corrupted, provided the corruption is fresh, independent and zero-mean. A block version was proposed for parallel hardware, but whether larger blocks actually converge faster was left open. We show the answer hinges on how the block is used: replacing the block sum with a block average collapses the analysis onto a single positive-semidefinite matrix, through which we prove that the guaranteed convergence improves monotonically with the batch size, with a total gain governed by the stable rank of the system matrix. We then address heterogeneous noise by introducing a noise-aware weighting that down-weights unreliable measurements, and prove it is strictly better than uniform weighting whenever the noise is not proportional to the row norms - a condition that essentially never holds in practice. The two improvements are compatible and their benefits combine. Finally, we show the adaptive step size interpolates automatically between a fast initial phase and a slowly vanishing tail that carries the error exactly to zero, and we explain how its hyperparameters can be estimated without knowing the true solution. Numerical experiments under sparse, heterogeneous noise illustrate these findings and confirm that the heuristic estimates produce effective step sizes.

Figures

Figures reproduced from arXiv: 2607.16003 by the authors.

**Figure 1.** Anatomy of one AABK iteration. Starting from xk = ∇f ∗ (x ∗ k ), the method ○1 samples a batch Bk = (i1, . . . , iτ ) of τ rows i.i.d. from p (with replacement, so a row may recur—here i1 = i3); ○2 computes in parallel one residual term gj = wij D aij ,xk E −˜b (k) j ∥aij ∥ 2 aij per draw, each using a fresh noisy value ˜b (k) j = bij + ε (k) j (indexing noise by the draw j guarantees independence even when a row is… view at source ↗

**Figure 2.** A comparison of the six methods as described in Section 5.1 for [PITH_FULL_IMAGE:figures/full_fig_p016_2.png] view at source ↗

**Figure 3.** A comparison of the ABK and AABK methods as described in Section 5.1 for [PITH_FULL_IMAGE:figures/full_fig_p017_3.png] view at source ↗

Figures from the paper (3 more)

**Figure 4.** Figure 4: Pseudo-inverse reconstruction from noisy sinogram. [PITH_FULL_IMAGE:figures/full_fig_p018_4.png]

**Figure 5.** Figure 5: Comparison of relative error (left) and residual error (right) for different methods in [PITH_FULL_IMAGE:figures/full_fig_p018_5.png]

**Figure 6.** Figure 6: Ground truth solution and reconstruction by the different methods under heteroge [PITH_FULL_IMAGE:figures/full_fig_p019_6.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

32 extracted references · 3 linked inside Pith

[27]

Lionel Tondji, Idriss Tondji, and Dirk Lorenz. Adaptive bregman–kaczmarz: an ap- proach to solve linear inverse problems with independent noise exactly.Inverse Problems, 40(9):095006, 2024.(Cited on pages 2, 3, 5, 7, 8, 9, 14, 30, and 33)

2024
[24]

Faster randomized block sparse kaczmarz by averaging

Lionel Tondji and Dirk A Lorenz. Faster randomized block sparse kaczmarz by averaging. Numerical Algorithms, 93(4):1417–1451, 2023.(Cited on pages 3, 4, 5, 6, and 12)

2023
[1]

On greedy randomized Kaczmarz method for solving large sparse linear systems.SIAM Journal on Scientific Computing, 40(1):A592–A606, 2018.(Cited on page 3)

Zhong-Zhi Bai and Wen-Ting Wu. On greedy randomized Kaczmarz method for solving large sparse linear systems.SIAM Journal on Scientific Computing, 40(1):A592–A606, 2018.(Cited on page 3)

2018
[2]

On quantile randomized kaczmarz for linear systems with time-varying noise and corruption.arXiv preprint arXiv:2403.19874, 2024.(Cited on page 3) 20

Nestor Coria, Jamie Haddock, and Jaime Pacheco. On quantile randomized kaczmarz for linear systems with time-varying noise and corruption.arXiv preprint arXiv:2403.19874, 2024.(Cited on page 3) 20

arXiv 2024
[3]

Acceleration of randomized Kaczmarz method via the Johnson-Lindenstrauss lemma.Numerical Algorithms, 58:163–177, 2011.(Cited on page 3)

Yonina C Eldar and Deanna Needell. Acceleration of randomized Kaczmarz method via the Johnson-Lindenstrauss lemma.Numerical Algorithms, 58:163–177, 2011.(Cited on page 3)

2011
[4]

Springer Science & Business Media, 1996.(Cited on page 1)

Heinz Werner Engl, Martin Hanke, and Andreas Neubauer.Regularization of inverse problems, volume 375. Springer Science & Business Media, 1996.(Cited on page 1)

1996
[5]

Algebraic reconstruction tech- niques (art) for three-dimensional electron microscopy and x-ray photography.Journal of theoretical Biology, 29(3):471–481, 1970.(Cited on page 2)

Richard Gordon, Robert Bender, and Gabor T Herman. Algebraic reconstruction tech- niques (art) for three-dimensional electron microscopy and x-ray photography.Journal of theoretical Biology, 29(3):471–481, 1970.(Cited on page 2)

1970
[6]

Gower, Denali Molitor, Jacob Moorman, and Deanna Needell

Robert M. Gower, Denali Molitor, Jacob Moorman, and Deanna Needell. On adaptive sketch-and-project for solving linear systems.SIAM Journal on Matrix Analysis and Applications, 42(2):954–989, 2021.(Cited on page 3)

2021

Show all 32 references

[7]

Greed works: An improved analysis of sampling Kaczmarz- Motzkin.SIAM Journal on Mathematics of Data Science, 3(1):342–368, 2021.(Cited on page 3)

Jamie Haddock and Anna Ma. Greed works: An improved analysis of sampling Kaczmarz- Motzkin.SIAM Journal on Mathematics of Data Science, 3(1):342–368, 2021.(Cited on page 3)

2021
[8]

Quantile- based iterative methods for corrupted systems of linear equations.SIAM Journal on Matrix Analysis and Applications, 43(2):605–637, 2022.(Cited on page 3)

Jamie Haddock, Deanna Needell, Elizaveta Rebrova, and William Swartworth. Quantile- based iterative methods for corrupted systems of linear equations.SIAM Journal on Matrix Analysis and Applications, 43(2):605–637, 2022.(Cited on page 3)

2022
[9]

Kaczmarz

S. Kaczmarz. Angen¨ aherte Aufl¨ osung von Systemen linearer Gleichungen.Bull. Internat. Acad. Polon. Sci. Lettres A, pages 355–357, 1937.(Cited on page 2)

1937
[10]

An accelerated randomized Kaczmarz algorithm.Mathematics of Computation, 85(297):153–178, 2016.(Cited on page 3)

Ji Liu and Stephen Wright. An accelerated randomized Kaczmarz algorithm.Mathematics of Computation, 85(297):153–178, 2016.(Cited on page 3)

2016
[11]

The linearized Bregman method via split feasibility problems: analysis and generalizations.SIAM Journal on Imaging Sciences, 7(2):1237–1262, 2014.(Cited on pages 2, 3, and 10)

Dirk A Lorenz, Frank Sch¨ opfer, and Stephan Wenger. The linearized Bregman method via split feasibility problems: analysis and generalizations.SIAM Journal on Imaging Sciences, 7(2):1237–1262, 2014.(Cited on pages 2, 3, and 10)

2014
[12]

An optimal scheduled learning rate for a random- ized kaczmarz algorithm.SIAM Journal on Matrix Analysis and Applications, 44(1):312– 330, 2023.(Cited on pages 3, 8, 30, and 33)

Nicholas F Marshall and Oscar Mickelin. An optimal scheduled learning rate for a random- ized kaczmarz algorithm.SIAM Journal on Matrix Analysis and Applications, 44(1):312– 330, 2023.(Cited on pages 3, 8, 30, and 33)

2023
[13]

Randomized kaczmarz with averaging.BIT Numerical Mathematics, 61(1):337–359, 2021.(Cited on pages 3 and 4)

Jacob D Moorman, Thomas K Tu, Denali Molitor, and Deanna Needell. Randomized kaczmarz with averaging.BIT Numerical Mathematics, 61(1):337–359, 2021.(Cited on pages 3 and 4)

2021
[14]

Mueller and Samuli Siltanen.Linear and nonlinear inverse problems with practical applications, volume 10 ofComputational Science & Engineering

Jennifer L. Mueller and Samuli Siltanen.Linear and nonlinear inverse problems with practical applications, volume 10 ofComputational Science & Engineering. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2012.(Cited on page 1)

2012
[15]

Faster randomized block kaczmarz algorithms.SIAM Journal on Matrix Analysis and Applications, 40(4):1425–1452, 2019.(Cited on page 3)

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

2019
[16]

Randomized kaczmarz solver for noisy linear systems.BIT Numerical Mathematics, 50(2):395–403, 2010.(Cited on pages 2, 3, and 6) 21

Deanna Needell. Randomized kaczmarz solver for noisy linear systems.BIT Numerical Mathematics, 50(2):395–403, 2010.(Cited on pages 2, 3, and 6) 21

2010
[17]

Paved with good intentions: analysis of a randomized block Kaczmarz method.Linear Algebra and its Applications, 441:199–221, 2014.(Cited on page 3)

Deanna Needell and Joel A Tropp. Paved with good intentions: analysis of a randomized block Kaczmarz method.Linear Algebra and its Applications, 441:199–221, 2014.(Cited on page 3)

2014
[18]

Tyrrell Rockafellar.Convex analysis, volume No

R. Tyrrell Rockafellar.Convex analysis, volume No. 28 ofPrinceton Mathematical Series. Princeton University Press, Princeton, NJ, 1970.(Cited on page 9)

1970
[19]

Linear convergence of the randomized sparse kaczmarz method.Mathematical Programming, 173(1):509–536, 2019.(Cited on pages 2, 3, and 10)

Frank Sch¨ opfer and Dirk A Lorenz. Linear convergence of the randomized sparse kaczmarz method.Mathematical Programming, 173(1):509–536, 2019.(Cited on pages 2, 3, and 10)

2019
[20]

Extended ran- domized kaczmarz method for sparse least squares and impulsive noise problems.Linear Algebra and its Applications, 652:132–154, 2022.(Cited on pages 2 and 10)

Frank Sch¨ opfer, Dirk A Lorenz, Lionel Tondji, and Maximilian Winkler. Extended ran- domized kaczmarz method for sparse least squares and impulsive noise problems.Linear Algebra and its Applications, 652:132–154, 2022.(Cited on pages 2 and 10)

2022
[21]

A weighted randomized Kaczmarz method for solving linear systems

Stefan Steinerberger. A weighted randomized Kaczmarz method for solving linear systems. Mathematics of Computation, 90(332):2815–2826, 2021.(Cited on page 3)

2021
[22]

Quantile-based random Kaczmarz for corrupted linear systems of equations.Information and Inference: A Journal of the IMA, 12(1):448–465, 2023.(Cited on page 3)

Stefan Steinerberger. Quantile-based random Kaczmarz for corrupted linear systems of equations.Information and Inference: A Journal of the IMA, 12(1):448–465, 2023.(Cited on page 3)

2023
[23]

A randomized kaczmarz algorithm with expo- nential convergence.Journal of Fourier Analysis and Applications, 15(2):262–278, 2009

Thomas Strohmer and Roman Vershynin. A randomized kaczmarz algorithm with expo- nential convergence.Journal of Fourier Analysis and Applications, 15(2):262–278, 2009. (Cited on pages 2, 3, and 4)

2009
[25]

An accelerated randomized bregman- kaczmarz method for strongly convex linearly constraint optimization

Lionel Tondji, Dirk A Lorenz, and Ion Necoara. An accelerated randomized bregman- kaczmarz method for strongly convex linearly constraint optimization. In2023 European Control Conference (ECC), pages 1–6. IEEE, 2023.(Cited on page 3)

2023
[26]

Acceleration and restart for the random- ized bregman-kaczmarz method.Linear Algebra and its Applications, 699:508–538, 2024

Lionel Tondji, Ion Necoara, and Dirk A Lorenz. Acceleration and restart for the random- ized bregman-kaczmarz method.Linear Algebra and its Applications, 699:508–538, 2024. (Cited on page 3)

2024
[28]

Linear convergence of a weighted randomized sparse kaczmarz method

Lionel N Tondji, Maximilian Winkler, and Dirk A Lorenz. Linear convergence of a weighted randomized sparse kaczmarz method. InConference: International Conference on Computational Harmonic Analysis, 2021.(Cited on page 3)

2021
[29]

PhD thesis, Technische Universit¨ at Braunschweig, 2024.(Cited on pages 3 and 5)

Lionel Ngoupeyou Tondji.Advances in Bregman-Kaczmarz Methods: Accelerations and Inconsistency. PhD thesis, Technische Universit¨ at Braunschweig, 2024.(Cited on pages 3 and 5)

2024
[30]

Quantile-based random sparse Kaczmarz for corrupted, noisy linear inverse systems.arXiv preprint arXiv:2206.07356, 2022.(Cited on page 3) 22

Lu Zhang, Hongxia Wang, and Hui Zhang. Quantile-based random sparse Kaczmarz for corrupted, noisy linear inverse systems.arXiv preprint arXiv:2206.07356, 2022.(Cited on page 3) 22

2022 arXiv
[31]

A weighted randomized sparse kaczmarz method for solving linear systems.arXiv preprint arXiv:2306.06813, 2023.(Cited on page 3)

Lu Zhang, Ziyang Yuan, Hongxia Wang, and Hui Zhang. A weighted randomized sparse kaczmarz method for solving linear systems.arXiv preprint arXiv:2306.06813, 2023.(Cited on page 3)

2023 arXiv
[32]

Randomized extended kaczmarz for solving least squares.SIAM Journal on Matrix Analysis and Applications, 34(2):773–793, 2013

Anastasios Zouzias and Nikolaos M Freris. Randomized extended kaczmarz for solving least squares.SIAM Journal on Matrix Analysis and Applications, 34(2):773–793, 2013. (Cited on page 2) 23 Appendix A Monotone acceleration for the optimal weights: proof of Proposition 2.2(iii) ...

2013

Pith tools

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

[1] [27]

Lionel Tondji, Idriss Tondji, and Dirk Lorenz. Adaptive bregman–kaczmarz: an ap- proach to solve linear inverse problems with independent noise exactly.Inverse Problems, 40(9):095006, 2024.(Cited on pages 2, 3, 5, 7, 8, 9, 14, 30, and 33)

2024

[2] [24]

Faster randomized block sparse kaczmarz by averaging

Lionel Tondji and Dirk A Lorenz. Faster randomized block sparse kaczmarz by averaging. Numerical Algorithms, 93(4):1417–1451, 2023.(Cited on pages 3, 4, 5, 6, and 12)

2023

[3] [1]

On greedy randomized Kaczmarz method for solving large sparse linear systems.SIAM Journal on Scientific Computing, 40(1):A592–A606, 2018.(Cited on page 3)

Zhong-Zhi Bai and Wen-Ting Wu. On greedy randomized Kaczmarz method for solving large sparse linear systems.SIAM Journal on Scientific Computing, 40(1):A592–A606, 2018.(Cited on page 3)

2018

[4] [2]

On quantile randomized kaczmarz for linear systems with time-varying noise and corruption.arXiv preprint arXiv:2403.19874, 2024.(Cited on page 3) 20

Nestor Coria, Jamie Haddock, and Jaime Pacheco. On quantile randomized kaczmarz for linear systems with time-varying noise and corruption.arXiv preprint arXiv:2403.19874, 2024.(Cited on page 3) 20

arXiv 2024

[5] [3]

Acceleration of randomized Kaczmarz method via the Johnson-Lindenstrauss lemma.Numerical Algorithms, 58:163–177, 2011.(Cited on page 3)

Yonina C Eldar and Deanna Needell. Acceleration of randomized Kaczmarz method via the Johnson-Lindenstrauss lemma.Numerical Algorithms, 58:163–177, 2011.(Cited on page 3)

2011

[6] [4]

Springer Science & Business Media, 1996.(Cited on page 1)

Heinz Werner Engl, Martin Hanke, and Andreas Neubauer.Regularization of inverse problems, volume 375. Springer Science & Business Media, 1996.(Cited on page 1)

1996

[7] [5]

Algebraic reconstruction tech- niques (art) for three-dimensional electron microscopy and x-ray photography.Journal of theoretical Biology, 29(3):471–481, 1970.(Cited on page 2)

Richard Gordon, Robert Bender, and Gabor T Herman. Algebraic reconstruction tech- niques (art) for three-dimensional electron microscopy and x-ray photography.Journal of theoretical Biology, 29(3):471–481, 1970.(Cited on page 2)

1970

[8] [6]

Gower, Denali Molitor, Jacob Moorman, and Deanna Needell

Robert M. Gower, Denali Molitor, Jacob Moorman, and Deanna Needell. On adaptive sketch-and-project for solving linear systems.SIAM Journal on Matrix Analysis and Applications, 42(2):954–989, 2021.(Cited on page 3)

2021