Pith. sign in

REVIEW 3 major objections 6 minor 1 cited by

Randomized Kaczmarz methods for t-product tensor linear systems with factorized operators

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

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

Pith's one-line read Randomized projections provably solve factorized tensor systems

desk verdict Solid algorithmic extension with a genuine proof bug in the central convergence rate; worth refereeing but needs a fix. read the letter →

arxiv 2412.10583 v1 pith:EPJ273HR submitted 2024-12-13 math.NA cs.NA

Alejandra Castillo , Jamie Haddock , Iryna Hartsock , Paulina Hoyos , Lara Kassab , Alona Kryshchenko , Kamila Larripa , Deanna Needell
show 2 more authors
Shambhavi Suryanarayanan Karamatou Yacoubou-Djima
This is my paper · ORCID
classification math.NAcs.NA MSC 65F1065F2015A6968W20
keywords randomizedKaczmarzt-producttensorlinearsystemsfactorizedoperatorsblocksamplingleast-squaresconvergenceinexpectationimagedeblurring
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 extends the randomized Kaczmarz method, a simple row-projection iteration for linear systems, to tensor equations of the form $\mathcal{U}\mathcal{V}\mathcal{X}=\mathcal{Y}$ where multiplication is the t-product and the operator is given as two factors. It proposes two interlaced block-randomized algorithms, FacTBRK for consistent systems and FacTBREK for systems whose outer equation is inconsistent, and proves that both converge at least linearly in expectation. If true, this gives a structured solver for regression problems whose operator naturally factors, such as images or videos degraded by two sequential blur kernels, without ever forming the product operator $\mathcal{U}\mathcal{V}$. The convergence rates are explicit in contraction constants that depend on the sampling distribution and the smallest singular values of the factor projections.

What carries the argument

The load-bearing object is the tensor block projection $\mathcal{P}_{\mathcal{M}}=\mathcal{M}^*(\mathcal{M}\mathcal{M}^*)^{-1}\mathcal{M}$, applied to row slices of $\mathcal{U}$ and $\mathcal{V}$; under the t-product each update projects the current iterate onto the solution set of a sampled block subsystem. The algorithms interlace these projections: a block randomized Kaczmarz step on $\mathcal{U}\mathcal{Z}=\mathcal{Y}$ refreshes $\mathcal{Z}^{(t)}$, and a block randomized Kaczmarz step on $\mathcal{V}\mathcal{X}=\mathcal{Z}^{(t)}$ uses the newest $\mathcal{Z}^{(t)}$ as the measurement for $\mathcal{X}$. The extended variant adds an update on $\mathcal{W}^{(t)}$ that drives toward the component of $\mathcal{Y}$ orthogonal to the range of $\mathcal{U}$, mirroring the randomized extended Kaczmarz correction for inconsistent systems. The contraction constants $\alpha_\mathcal{U}$, $\alpha_\mathcal{V}$, and $\beta_\mathcal{U}$ in Definition 4 are spectral gaps of expected block-circulant projection tensors, and they convert block-wise residual reduction into a global linear-rate bound.

What would settle it

Construct a small system (for example $p=2$, $m=m_1=n=l=2$) with $\mathcal{V}$ chosen so that $\mathrm{bcirc}(\mathcal{V})$ is rank-deficient and $\mathcal{Z}^\ddagger$ lies outside its range, while $\mathcal{Y}=\mathcal{U}\mathcal{Z}^\ddagger$ is consistent, and run FacTBREK. If the relative error $\mathbb{E}\|\mathcal{X}^{(t)}-\mathcal{X}^\ddagger\|_F/\|\mathcal{X}^\ddagger\|_F$ does not decrease linearly in expectation, the inner-consistency assumption is shown to be necessary; the same construction with full-rank $\mathcal{V}$ should satisfy the theorem's bound.

Watch

Extended reading notes

Core claim

The central result is Theorem 1, a pair of explicit expected-error bounds. Under the assumptions that the outer system $\mathcal{U}\mathcal{Z}=\mathcal{Y}$ has a unique solution (for FacTBRK) or a unique least-squares minimizer (for FacTBREK), and that the inner system $\mathcal{V}\mathcal{X}=\mathcal{Z}^\ddagger$ is consistent, each algorithm's $t$-th iterate satisfies an inequality of the form $\mathbb{E}\|\mathcal{X}^{(t)}-\mathcal{X}^\ddagger\|_F^2 \le (\alpha_\mathcal{V}^t + \theta_\mathcal{V}(\cdots))\,\|\mathcal{X}^\ddagger\|_F^2$, with contraction constants $\alpha_\mathcal{U}$, $\alpha_\mathcal{V}$, and $\beta_\mathcal{U}$ defined as one minus the smallest eigenvalue of an expected block-circulant projection. Thus FacTBRK reaches the minimum-Frobenius-norm solution of a consistent factorized system, and FacTBREK reaches the least-squares solution when the outer system is inconsistent, both at an exponential rate in expectation. The proof interlocks one-step contractions for the inner and outer projections and uses a tensor analog of the Pythagorean split for projected errors.

Load-bearing premise

The central claim collapses if the inner system $\mathcal{V}\mathcal{X}=\mathcal{Z}^\ddagger$ is not exactly consistent, since both convergence theorems assume it; the sampling distribution must also keep the expected projection positive definite so the contraction constants stay strictly below one.

Editorial extensions

If this is right

  • For a consistent factorized tensor system, FacTBRK reaches the minimal-Frobenius-norm solution, and the convergence rate is governed by the worst of the inner and outer contraction constants.
  • For an inconsistent outer system, FacTBREK still reaches the least-squares solution, provided the inner system $\mathcal{V}\mathcal{X}=\mathcal{Z}^\ddagger$ is consistent.
  • The block formulation allows arbitrary row-slice blocks of $\mathcal{U}$ and $\mathcal{V}$, and the numerical experiments show that larger outer blocks generally converge faster, though with more variance.
  • When the tensor dimension is $p=1$ the methods reduce to matrix factorized Kaczmarz algorithms, and when $\mathcal{V}=\mathcal{I}$ with singleton blocks, FacTBRK recovers the tensor randomized Kaczmarz bound up to a constant.
  • Applied to a twice-blurred video deblurring task, the methods treat the two blur kernels as the factors $\mathcal{U}$ and $\mathcal{V}$ and recover frames within a residual error of $10^{-2}$ in the reported experiment.

Reading between the lines

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

  • An implication the authors leave implicit is that their theorems do not cover noise in the factorization itself: if the least-squares minimizer $\mathcal{Z}^\ddagger$ falls outside the range of $\mathcal{V}$, neither algorithm is guaranteed to converge, and the appendix's divergence experiments support reading the consistency assumption as a necessary condition.
  • A natural testable extension is to corrupt both factors, e.g., $\mathcal{Y}=\mathcal{U}\mathcal{V}\mathcal{X}+\mathcal{E}$ and $\mathcal{Z}=\mathcal{V}\mathcal{X}+\mathcal{F}$; the current bounds cover only $\mathcal{E}$, so comparing convergence horizons as $\|\mathcal{F}\|_F$ grows would map the method's practical limits.
  • Because the t-product is defined through block-circulant matrices, analogous interlaced algorithms might be lifted to fourth-order tensors via block-Toeplitz constructions, though the projection identities would need to be reworked.
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.

Referee Report

3 major / 6 minor

Summary. The paper proposes two randomized Kaczmarz methods for tensor linear systems of the form U V X = Y under the t-product, where the operator is factorized as a product of two tensors. The first method (FacTBRK) interlaces block randomized Kaczmarz steps on the outer system U Z = Y and the inner system V X = Z, and is claimed to converge linearly in expectation to the minimal Frobenius-norm solution when both systems are consistent. The second method (FacTBREK) adds an extended Kaczmarz step to handle inconsistency in the outer system, and is claimed to converge to the least-squares solution of the outer problem under the assumption that the inner system is consistent with the outer least-squares solution. The paper provides explicit contraction bounds in Theorem 1, supported by lemmas on tensor projections and sampling, and presents numerical experiments on synthetic data and a video deblurring application. The main contribution is the extension of factorized randomized Kaczmarz theory from matrix systems to t-product tensor systems with block sampling.

Significance. If the convergence claims were fully established, the paper would be a useful extension of the factorized Kaczmarz framework [22] to t-product tensor systems, with the added generality of block sampling. The algorithmic constructions are natural, the tensor-to-matrix reduction via bcirc is standard, and the numerical experiments, including the appended divergence cases, provide an honest picture of the method's scope. The paper also ships self-contained proofs of the supporting lemmas, and the dependence of the bounds on the sampling distribution and tensor singular values is explicit and not fitted to data. However, the central quantitative claims in Theorems 1 and 2 are not currently supported because the proofs contain invalid convolution-sum estimates. The qualitative linear-in-expectation convergence may be salvageable with corrected bounds, but the explicit rates as stated are not established, which diminishes the paper's contribution until the proofs are repaired.

major comments (3)
  1. [Section 2.4, proof of Theorem 1(1)] The inequality used to bound the convolution sum is invalid. In the proof, the term Σ_{s=1}^t α_U^s α_V^{t-s} is bounded by α_max^t Σ_{s=1}^t α_min^s, where α_min = min{α_U/α_V, α_V/α_U}. When α_U > α_V, we have α_U = α_max and α_V = α_min α_max, so α_U^s α_V^{t-s} = α_max^t α_min^{t-s}, not α_max^t α_min^s. The sum is therefore α_max^t Σ_{r=0}^{t-1} α_min^r, which is larger than the claimed bound. For example, with α_U = 0.5, α_V = 0.25, and t = 2, the true sum is 0.5·0.25 + 0.5^2 = 0.375, while the paper's upper bound is α_max^2(α_min + α_min^2) = 0.25·0.75 = 0.1875. Thus the bound in Theorem 1(1), which uses α_max^t α_min/(1−α_min), is not an upper bound on the error in general, and the stated rate is not proven.
  2. [Section 2.4, proof of Theorem 1(2)] The step replacing the convolution sum by its middle term is not valid. The proof bounds Σ_{s=0}^{t} α_V^s γ(t−s) by (t+1)α_V^{⌊t/2⌋}γ(⌊t/2⌋), but this requires each term α_V^s γ(t−s) to be bounded by the middle term, which is false. Since γ(t−s) is a sum of exponentials, the product α_V^s γ(t−s) is generally maximized at an endpoint. For example, take α_V = 0.9, α_U = 0.1, β_U = 0.2, θ_U = 1, and σ_max^2(bcirc(U)) = 1, so γ(t) = 0.1^t + 0.2^t. At t = 2, the sum is γ(2) + 0.9γ(1) + 0.81γ(0) = 0.05 + 0.27 + 1.62 = 1.94, while the claimed bound is 3·0.9·γ(1) = 0.81. This is not an upper bound. Consequently, the explicit rate in Theorem 1(2), which involves α_V^{⌊t/2⌋}α_U^{⌊t/2⌋}, is not established and is in fact too optimistic; the correct bound would involve an endpoint maximum and yields a slower effective rate.
  3. [Section 2.3, proof of Theorem 2] The same convolution error appears in the proof of Theorem 2 when β_U > α_U. The proof bounds Σ_{s=1}^t β_U^s α_U^{t-s} by φ_max^t Σ_{s=1}^t φ_min^s, where φ_min = min{α_U/β_U, β_U/α_U}. If β_U > α_U, then β_U = φ_max and α_U = φ_min φ_max, so β_U^s α_U^{t-s} = φ_max^t φ_min^{t-s}. The sum is φ_max^t Σ_{r=0}^{t-1} φ_min^r, not φ_max^t Σ_{s=1}^t φ_min^s. For example, α_U = 0.05, β_U = 0.5, t = 1 gives the true sum 0.5, while the paper's bound is φ_max φ_min = 0.05. Since Theorem 2 is used as the γ(t) estimate inside Theorem 1(2), this compounds the issue in the main convergence claim.
minor comments (6)
  1. [Section 2.4, proof of Theorem 1(2)] The summation in the recursion is typeset with a confusing index: "Σ_{t=0}^{t} α_s^V γ(t−s)" should read "Σ_{s=0}^{t} α_V^s γ(t−s)".
  2. [Section 3.2, Figure 11] The text and figure caption refer to "FacTRK" when describing the deblurring experiment; this appears to be a typo for FacTBRK (or FacTBREK), and should be corrected.
  3. [Definition 4] The definitions of θ_U and θ_V are dense and the two cases in the conditional are not explicitly labeled; adding a short explanation of when each case applies would improve readability.
  4. [Lemma 3] The spelling "Cauchy-Schwartz" should be "Cauchy-Schwarz".
  5. [Lemma 4] The statement refers to ∥X(0)−X∥_F but does not explicitly introduce X(0) as the initial iterate; this should be stated for clarity.
  6. [Section 3.1.2, Table 1] The table uses color coding (shaded gray cells) to indicate cases where the theorem's assumptions fail; if the paper is printed in black and white, this information should also be conveyed textually.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; the convergence bounds are derived from explicit contraction constants and standard tensor-matrix lemmas, with no fitted parameters or self-referential predictions.

full rationale

The paper's central claims are convergence-rate bounds for two randomized algorithms. Each bound is obtained by composing contraction inequalities: Lemma 2 bounds projected-error decay using the minimum singular value of the expected block-circulant projection, Lemma 3 bounds the noise term, Lemma 4 gives the single-step TBRK recursion, Lemma 6 transfers the outer-system error into the inner-system update, and Theorem 2 supplies the TBREK bound used in the recursion for FacTBREK. All constants (alpha_U, alpha_V, beta_U, theta_U, theta_V) are defined directly from the problem data and sampling distribution, not fitted to any observed trajectory, so no 'prediction' is statistically forced. The numerical experiments generate systems that satisfy the theorem's assumptions and then measure relative error, which is a validation exercise rather than a circular derivation. The paper does rely on prior work, notably the tensor Kaczmarz method of Ma and Molitor [20] and the factorized matrix Kaczmarz method of Ma, Needell, and Ramdas [22], but these are used as background and as special cases (e.g., Remark 3), not as the load-bearing justification of the new bounds. The explicit consistency assumption on the inner system V X = Z^dagger is stated rather than smuggled in, and the appendix's divergence examples honestly mark where the theorem's assumptions fail. The skeptic's identified flaw in the proof of Theorem 1(2) concerns the validity of a convolution-sum upper bound; that is a potential mathematical correctness issue, not a circularity issue, because the offending inequality is not equivalent to the theorem's input by construction. No step in the derivation reduces to a self-citation chain or to a fitted parameter renamed as a result. Therefore the appropriate circularity score is 0.

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

The methods introduce no new physical or mathematical entities. All constants in the bounds are defined from the tensor data and sampling distribution. The only 'cost' is the standard t-product framework and the explicit assumptions listed above.

assumptions (5)
  • domain assumption The sampled blocks of U and V are wide enough that U_mu U_mu* and V_nu V_nu* are invertible for all sampled blocks.
    Needed to define the projection updates in Algorithms 2 and 3; stated as Assumption 1.
  • standard math A tensor linear system is equivalent to its block-circulant matrix form.
    Used throughout to transfer singular value and least-squares arguments from matrices to tensors; stated as Fact 1.
  • domain assumption For Theorem 1, the outer system U Z = Y (consistent case) or the least-squares minimizer Z* (inconsistent case) makes the inner system V X = Z consistent, with unique minimal-norm solution X*.
    This is the restriction that limits the inconsistent-regime claim; the paper acknowledges divergence when it fails.
  • domain assumption The random samples mu_t, nu_t, and l_t are independent across iterations.
    Used to factorize expectations in the convergence proofs in Section 2.
  • domain assumption The sampling distribution yields sigma_min(E[bcirc(P)]) > 0, so alpha_U, alpha_V, and beta_U are strictly less than 1.
    Needed for nontrivial contraction in Lemma 4 and Theorem 2; not explicitly stated but required.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Randomized Kaczmarz methods for t-product tensor linear systems with factorized operators." pith.science (2026). https://pith.science/paper/EPJ273HR

@misc{pith2026241210583,
  author       = {Pith},
  title        = {Pith review of: Randomized Kaczmarz methods for t-product tensor linear systems with factorized operators},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/EPJ273HR}},
  note         = {Machine review of arXiv:2412.10583}
}
abstract

Randomized iterative algorithms, such as the randomized Kaczmarz method, have gained considerable popularity due to their efficacy in solving matrix-vector and matrix-matrix regression problems. Our present work leverages the insights gained from studying such algorithms to develop regression methods for tensors, which are the natural setting for many application problems, e.g., image deblurring. In particular, we extend the randomized Kaczmarz method to solve a tensor system of the form $\mathbf{\mathcal{A}}\mathcal{X} = \mathcal{B}$, where $\mathcal{X}$ can be factorized as $\mathcal{X} = \mathcal{U}\mathcal{V}$, and all products are calculated using the t-product. We develop variants of the randomized factorized Kaczmarz method for matrices that approximately solve tensor systems in both the consistent and inconsistent regimes. We provide theoretical guarantees of the exponential convergence rate of our algorithms, accompanied by illustrative numerical simulations. Furthermore, we situate our method within a broader context by linking our novel approaches to earlier randomized Kaczmarz methods.

Figures

Figures reproduced from arXiv: 2412.10583 by the authors.

Figure 1
Figure 1. Relative error ∥X (t)−X ‡ ∥F /∥X ‡ ∥F vs iteration t of FacTBRK and FacTBREK with outer block sizes |µt| ∈ {1, 5, 10} and inner system block size |νt| = 1 on inconsistent tensor linear system (left) and consistent tensor linear system (right) [PITH_FULL_IMAGE:figures/full_fig_p014_1.png] view at source ↗
Figure 2
Figure 2. (Left) Relative error ∥X (t) − X ‡ ∥F /∥X ‡ ∥F vs iteration t of FacTBRK on consistent linear system and FacTBREK on inconsistent linear system with outer block sizes |µt| ∈ {1, 5, 10} and inner system block size |νt| = 1. (Right) Relative error ∥X (t) − X ‡ ∥F /∥X ‡ ∥F vs iteration t of FacTBREK on consistent and inconsistent linear systems with outer block sizes |µt| ∈ {1, 5, 10} and inner system block size |νt| =… view at source ↗
Figure 3
Figure 3. Relative error ∥X (t) − X ‡ ∥F /∥X ‡ ∥F vs iteration t of FacTBRK on consistent linear system when A is under-determined, U is over-determined and V is under-determined. We consider outer block sizes |µt| ∈ {1, 3, 5} and inner system block size (Upper Left) |νt| = 1, (Upper Right) |νt| = 3, (Lower) |νt| = 5. In Figures (3, 4 and 5 for FacTBRK, and 6, 7 and 8 for FacTBREK), we consider the cases when the subsystem wi… view at source ↗
Figures from the paper (14 more)
Figure 4
Figure 4. Figure 4: Relative error ∥X (t) − X ‡ ∥F /∥X ‡ ∥F vs iteration t of FacTBRK on consistent linear system when A is over-determined, U is over-determined and V is under-determined. We consider outer block sizes |µt| ∈ {1, 5, 10, 15} and inner system block size (Upper Left) |νt| = …
Figure 5
Figure 5. Figure 5: Relative error ∥X (t) − X ‡ ∥F /∥X ‡ ∥F vs iteration t of FacTBRK on consistent linear system when A is over-determined and both U and V are over-determined. We consider outer block sizes |µt| ∈ {1, 5, 10, 20, 25} and inner system block size (Upper Left) |νt| = 1, (Upp…
Figure 6
Figure 6. Figure 6: Relative error ∥X (t) − X ‡ ∥F /∥X ‡ ∥F vs iteration t of FacTBREK on consistent linear system when A is under-determined, U is over-determined and V is under-determined. We consider outer block sizes |µt| ∈ {1, 3, 5} and inner system block size (Upper Left) |νt| = 1, …
Figure 7
Figure 7. Figure 7: Relative error ∥X (t) − X ‡ ∥F /∥X ‡ ∥F vs iteration t of FacTBREK on consistent linear system when A is over-determined, U is over-determined and V is under-determined. We consider outer block sizes |µt| ∈ {1, 5, 10, 15} and inner system block size (Upper Left) |νt| =…
Figure 8
Figure 8. Figure 8: Relative error ∥X (t) − X ‡ ∥F /∥X ‡ ∥F vs iteration t of FacTBREK on consistent linear system when A is over-determined, and both U and V are over-determined. We consider outer block sizes |µt| ∈ {1, 5, 10, 20, 25} and inner system block size (Upper Left) |νt| = 1, (U…
Figure 9
Figure 9. Figure 9: Relative error ∥X (t) − X ‡ ∥F /∥X ‡ ∥F vs iteration t of FacTBRK on a consistent linear system for outer block sizes |µt| ∈ {1, 5, 10} and constant inner system block size |νt| = 1 for different types of block partition. The notation |µt| means “average block size |µt…
Figure 10
Figure 10. Figure 10: (Left) Relative error ∥X (t) − X ‡ ∥F /∥X ‡ ∥F vs iteration t of FacTBRK on the consistent tensor system UVX = Y with |µt| ∈ {1, 5, 10} and |νt| = 1 and FacTBRK on the equivalent matricized system bcirc(U)bcirc(V)unfold(X ) = unfold(Y) with |µt| ∈ {p, 5p, 10p} and |νt…
Figure 11
Figure 11. Figure 11: Deblurring of twice sequentially blurred video data using the FacTRK. (Left) Residual error of FacTRK iterates for two different initializations. (Right) Frames from original video (top row), twice blurred frames (second row), frames recovered using FacTRK (third and …
Figure 12
Figure 12. Figure 12: Relative error ∥X (t) − X ‡ ∥F /∥X ‡ ∥F vs iteration t of FacTBRK on consistent linear system when A is under-determined, U is under-determined and V is over-determined. We consider outer block sizes |µt| ∈ {1, 5, 10} and inner system block size (Upper Left) |νt| = 1,…
Figure 13
Figure 13. Figure 13: Relative error ∥X (t) − X ‡ ∥F /∥X ‡ ∥F vs iteration t of FacTBRK on consistent linear system when A is under-determined and both U and V are under-determined. We consider outer block sizes |µt| ∈ {1, 5, 10} and inner system block size (Upper Left) |νt| = 1, (Upper Ri…
Figure 14
Figure 14. Figure 14: Relative error ∥X (t) − X ‡ ∥F /∥X ‡ ∥F vs iteration t of FacTBRK on consistent linear system when A is over-determined, U is under-determined and V is over-determined. We consider outer block sizes |µt| ∈ {1, 10, 20} and inner system block size (Upper Left) |νt| = 1,…
Figure 15
Figure 15. Figure 15: Relative error ∥X (t) −X ‡ ∥F /∥X ‡ ∥F vs iteration t of FacTBREK on consistent linear system when A is under-determined, U is under-determined and V is over-determined. We consider outer block sizes |µt| ∈ {1, 5, 10} and inner system block size (Upper Left) |νt| = 1,…
Figure 16
Figure 16. Figure 16: Relative error ∥X (t) −X ‡ ∥F /∥X ‡ ∥F vs iteration t of FacTBREK on consistent linear system when A is under-determined, and both U and V are under-determined. We consider outer block sizes |µt| ∈ {1, 5, 10} and inner system block size (Upper Left) |νt| = 1, (Upper R…
Figure 17
Figure 17. Figure 17: Relative error ∥X (t) −X ‡ ∥F /∥X ‡ ∥F vs iteration t of FacTBREK on consistent linear system when A is over-determined, U is under-determined and V is over-determined. We consider outer block sizes |µt| ∈ {1, 10, 20} and inner system block size (Upper Left) |νt| = 1,…

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

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

  1. Stochastic Gradient Descent for Incomplete Tensor Linear Systems

    math.NA 2025-10 conditional novelty 6.0 of 10

    A correction-term framework for SGD lets incomplete tensor linear systems be solved under column-block and frontal-slice missing models, with standard SGD convergence rates.

Reference graph

Works this paper leans on

36 extracted references · 34 canonical work pages · cited by 1 Pith paper

  1. [22]

    A. Ma, D. Needell, and A. Ramdas. Iterative methods for solving factorized linear systems. SIAM J. Matrix Anal. Appl. , 39(1):104–122, 2018

    work page 2018

  2. [1]

    W. Bao, F. Zhang, W. Li, Q. Wang, and Y. Gao. Randomized average Kaczmarz algorithm for tensor linear systems. Mathematics, 10(23), 2022

    work page 2022

  3. [2]

    Boyd and L

    S. Boyd and L. Vandenberghe. Convex optimization . Cambridge Univ. Press, 2004

    work page 2004

  4. [3]

    Chen and J

    X. Chen and J. Qin. Regularized Kaczmarz algorithms for tensor recovery. SIAM J. Imag. Sci. , 14(4):1439–1471, 2021

    work page 2021

  5. [4]

    Du, W.-T

    K. Du, W.-T. Si, and X.-H. Sun. Randomized extended average block Kaczmarz for solving least squares. SIAM J. Sci. Comput., 42(6):A3541–A3559, 2020

    work page 2020

  6. [5]

    Randomized regularized extended Kaczmarz algorithms for tensor recovery

    K. Du and X.-H. Sun. Randomized regularized extended Kaczmarz algorithms for tensor recovery. arXiv preprint arXiv:2112.08566, 2021

    work page Pith review arXiv 2021

  7. [6]

    Dumitrescu

    B. Dumitrescu. On the relation between the randomized extended Kaczmarz algorithm and coordinate descent. BIT Num. Math., pages 1–11, 2014

    work page 2014

  8. [7]

    Y. C. Eldar and D. Needell. Acceleration of randomized Kaczmarz method via the Johnson-Lindenstrauss lemma. Num. Algorithms, 58(2):163–177, 2011

    work page 2011

Show all 36 references
  1. [8]

    Gordon, R

    R. Gordon, R. Bender, and G. T. Herman. Algebraic reconstruction techniques (ART) for three-dimensional electron microscopy and X-ray photography. J. Theoret. Biol. , 29:471–481, 1970

    1970

  2. [9]

    Haddock, B

    J. Haddock, B. Jarman, and C. Yap. Paving the way for consensus: Convergence of block gossip algorithms. IEEE T. Inform. Theory, 68(11):7515–7527, 2022

    2022

  3. [10]

    Haddock and D

    J. Haddock and D. Needell. Randomized projections for corrupted linear systems. In AIP Conf. Proc. , volume 1978, page 470071. AIP Publishing LLC, 2018

    1978

  4. [11]

    Haddock and D

    J. Haddock and D. Needell. Randomized projection methods for linear systems with arbitrarily large sparse corruptions. SIAM J. Sci. Comput. , 41(5):S19–S36, 2019

    2019

  5. [12]

    Haddock, D

    J. Haddock, D. Needell, E. Rebrova, and W. Swartworth. Quantile-based iterative methods for corrupted systems of linear equations. SIAM J. Matrix Anal. Appl. , 43(3):605–637, 2022

    2022

  6. [13]

    Herman and L.B

    G.T. Herman and L.B. Meyer. Algebraic reconstruction techniques can be made computationally efficient. IEEE T. Med. Imag., 12(3):600–609, 1993

    1993

  7. [14]

    Huang and S.-Y

    G.-X. Huang and S.-Y. Zhong. Tensor randomized extended Kaczmarz methods for large inconsistent tensor linear equations with t-product. Num. Algorithms, pages 1–24, 2023

    2023

  8. [15]

    Kaczmarz

    S. Kaczmarz. Angen¨ aherte aufl¨ osung von systemen linearer gleichungen.Bulletin International de l’Acad´ emie Polonaise des Sciences et des Lettres , 35:355–357, 1937

    1937

  9. [16]

    M. E. Kilmer, K. Braman, N. Hao, and R. C. Hoover. Third-order tensors as operators on matrices: A theoretical and computational framework with applications in imaging. SIAM J. Matrix Anal. Appl. , 34(1):148–172, 2013

    2013

  10. [17]

    M. E. Kilmer and C. D. Martin. Factorization strategies for third-order tensors. Linear Algebra Appl. , 435(3):641–658, 2011

    2011

  11. [18]

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

    2014 arXiv

  12. [19]

    Y. Liu, J. Liu, Z. Long, and C. Zhu. Tensor regression. Springer, 2022

    2022

  13. [20]

    Ma and D

    A. Ma and D. Molitor. Randomized Kaczmarz for tensor linear systems. BIT Num. Math. , 62(1):171–194, 2022

    2022

  14. [21]

    A. Ma, D. Needell, and A. Ramdas. Convergence properties of the randomized extended Gauss–Seidel and Kaczmarz methods. SIAM J. Matrix Anal. Appl. , 36(4):1590–1604, 2015

    2015

  15. [23]

    J. D. Moorman, T. K. Tu, D. Molitor, and D. Needell. Randomized Kaczmarz with averaging. BIT Num. Math. , 2020

    2020

  16. [24]

    M. S. Morshed, M. S. Islam, and M. Noor-E-Alam. Accelerated sampling Kaczmarz Motzkin algorithm for the linear feasibility problem. J. Global Optim. , pages 1–22, 2019

    2019

  17. [25]

    Needell, N

    D. Needell, N. Srebro, and R. Ward. Stochastic gradient descent and the randomized Kaczmarz algorithm. Math. Program. A, 155(1):549–573, 2016

    2016

  18. [26]

    Needell and J

    D. Needell and J. A. Tropp. Paved with good intentions: Analysis of a randomized block Kaczmarz method. Linear Algebra Appl., 2013

    2013

  19. [27]

    Randomized Kaczmarz solver for noisy linear systems

    Deanna Needell. Randomized Kaczmarz solver for noisy linear systems. BIT Numer. Math. , 50(2):395–403, 2010

    2010

  20. [28]

    C. Popa. A fast Kaczmarz-Kovarik algorithm for consistent least-squares problems. Korean J. Comput. Appl. Math. , 8(1):9–26, 2001

    2001

  21. [29]

    C. Popa. A Kaczmarz-Kovarik algorithm for symmetric ill-conditioned matrices. An. S ¸tiint ¸. Univ. Ovidius Constant ¸a Ser. Mat., 12(2):135–146, 2004

    2004

  22. [30]

    C. Popa, T. Preclik, H. K¨ ostler, and U. R¨ ude. On Kaczmarz’s projection iteration as a direct solver for linear least squares problems. Linear Algebra Appl., 436(2):389–404, 2012

    2012

  23. [31]

    Savvides, C.-C

    A. Savvides, C.-C. Han, and M. B. Strivastava. Dynamic fine-grained localization in ad-hoc networks of sensors. In Proc. 7th Ann. Int. Conf. Mobile Computing and Networking , pages 166–179, 2001

    2001

  24. [32]

    Steinerberger

    S. Steinerberger. Quantile-based random Kaczmarz for corrupted linear systems of equations.Inform. and Infer., 12(1):448– 465, 2023

    2023

  25. [33]

    Strohmer and R

    T. Strohmer and R. Vershynin. A randomized Kaczmarz algorithm with exponential convergence. J. Fourier Anal. Appl. , 15(2):262, 2009

    2009

  26. [34]

    L. Tang, Y. Yu, Y. Zhang, and H. Li. Sketch-and-project methods for tensor linear systems. Num. Linear Algebra , 30(2):e2470, 2023. 24 Figure 12. Relative error ∥X (t) − X ‡∥F /∥X ‡∥F vs iteration t of FacTBRK on consistent linear system when A is under-determined, U is under-...

    2023

  27. [35]

    Zhang, J

    M. Zhang, J. Haddock, and D. Needell. Block matrix and tensor randomized Kaczmarz methods for linear feasibility problems, 2024

    2024

  28. [36]

    Zouzias and N

    A. Zouzias and N. M. Freris. Randomized extended Kaczmarz for solving least squares. SIAM J. Matrix Anal. Appl. , 34(2):773–793, 2013. Appendix A. A: Effect of different systems and different block sizes. (Continued) 25 Figure 13. Relative error ∥X (t) − X ‡∥F /∥X ‡∥F vs itera...

    2013

Pith tools

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