On convergence of residual-based extended randomized Kaczmarz methods for matrix equations

Jichao Wang; Jing Li; Lili Xing; Weiguo Li; Wendi Bao

arxiv: 2604.05726 · v1 · submitted 2026-04-07 · 🧮 math.NA · cs.NA

On convergence of residual-based extended randomized Kaczmarz methods for matrix equations

Wendi Bao , Jing Li , Lili Xing , Weiguo Li , Jichao Wang This is my paper

Pith reviewed 2026-05-10 18:43 UTC · model grok-4.3

classification 🧮 math.NA cs.NA

keywords randomized Kaczmarz methodmatrix equationsconvergence analysisNesterov momentuminconsistent systemsextended Kaczmarzresidual-based selection

0 comments

The pith

Residual-based randomized Kaczmarz methods converge for inconsistent matrix equations without full column rank assumptions.

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

The paper introduces a dual-space residual-based randomized extended Kaczmarz method for solving inconsistent matrix equations, along with a version accelerated by Nesterov momentum. It delivers a complete convergence analysis that avoids the standard requirement of full column rank on the coefficient matrices. Upper bounds on the convergence rates are derived, and a suitable range for the momentum parameters is identified. Experiments indicate that these approaches outperform prior methods, with the momentum variant showing particular gains.

Core claim

For inconsistent matrix equations, the dual-space residual-based randomized extended Kaczmarz method and its Nesterov momentum variant converge, with explicit upper bounds on their convergence rates provided in the absence of full column rank assumptions on the coefficient matrices. A feasible interval for the momentum parameters is also established.

What carries the argument

The residual-based randomized selection strategy in the extended Kaczmarz iteration operating in dual space, which supports convergence analysis without full column rank.

If this is right

The methods apply to inconsistent matrix equations where coefficient matrices lack full column rank.
Explicit upper bounds on convergence rates are available for both the basic and momentum-accelerated versions.
Momentum parameters can be safely chosen from an identified feasible interval to guarantee acceleration.
Numerical performance exceeds that of earlier randomized Kaczmarz variants, especially when momentum is added.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The convergence framework could be tested on other iterative solvers for inconsistent linear systems beyond matrix equations.
Adaptive tuning of the momentum parameter using observed residuals might further improve practical speed.
The dual-space residual approach may connect to block or multi-step variants of Kaczmarz methods.

Load-bearing premise

The randomized selection follows the specific probability distribution based on residual norms and the momentum parameter lies inside the derived feasible range.

What would settle it

A concrete counterexample showing divergence or failure to achieve the stated rates when the momentum parameter falls outside the feasible range or when row/column selection deviates from the residual-based probabilities, for an inconsistent matrix equation lacking full column rank.

read the original abstract

In this paper, for solving inconsistent matrix equations we propose a dual-space residual-based randomized extended Kaczmarz method and its version with Nesterov momentum. Without the full column rank assumptions on coefficient matrices, we provide a thorough convergence analysis, and derive upper bounds for the convergence rates of the new methods. A feasible range for the momentum parameters is determined. Numerical experiments demonstrate that the proposed methods are much more effective than the existing ones, especially the method with momentum.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Extends randomized Kaczmarz to inconsistent matrix equations via dual-space residuals and Nesterov momentum, with convergence rates proved without full column rank.

read the letter

The paper introduces a dual-space residual-based randomized extended Kaczmarz method for inconsistent matrix equations and a Nesterov-accelerated version of it. The central advance is the convergence analysis that removes the full column rank assumption on the coefficient matrices, which prior work often required. They derive explicit upper bounds on the expected convergence rates and identify a feasible interval for the momentum parameter that keeps the contraction factor strictly below one under their randomized selection rule. The experiments show the momentum variant outperforming earlier methods on the tested cases. The analysis looks solid: it works with the expected squared error contraction and uses the dual-space projection to manage inconsistency without rank restrictions. The momentum bounds come from ensuring the spectral radius condition holds for the given probabilities. This is useful incremental work in the randomized Kaczmarz literature. The main limitation is that the rates and guarantees depend on staying inside the momentum interval and using the stated selection probabilities; outside those choices the bounds do not apply, which is standard but limits plug-and-play use. The numerical tests are convincing for the examples chosen yet stay modest in scale and conditioning, so they do not fully stress the methods on the largest or worst-conditioned problems where such solvers are often applied. Readers working on iterative solvers for overdetermined or inconsistent linear and matrix systems in data science or imaging will get the most from it. The theory is grounded enough and the relaxation of the rank assumption is concrete enough that the paper merits peer review rather than a desk rejection.

Referee Report

0 major / 3 minor

Summary. The paper proposes a dual-space residual-based randomized extended Kaczmarz method (and its Nesterov-momentum variant) for inconsistent matrix equations AXB=C. It claims to establish convergence and explicit rate bounds without requiring full column rank on the coefficient matrices, by using residual projections in dual space to obtain a contraction mapping on the expected error; it also derives a feasible interval for the momentum parameter ensuring the spectral radius factor is strictly less than one under the given selection probabilities, and reports numerical superiority over existing methods.

Significance. If the central claims hold, the work meaningfully extends randomized iterative solvers for matrix equations by removing the full-rank restriction that limits applicability to many practical inconsistent systems. The dual-space formulation and explicit contraction-based bounds provide a clean theoretical framework, while the momentum analysis and numerical gains highlight acceleration potential. Strengths include the parameter-free derivation of the feasible momentum range from the iteration rules and the focus on reproducible rate bounds.

minor comments (3)

[§2.2] §2.2, Algorithm 1: the update for the dual residual projection step uses an implicit normalization that should be written explicitly to match the probability definition in Eq. (7).
[Theorem 3.1] Theorem 3.1: the statement of the contraction factor omits the dependence on the inconsistency measure; adding a brief remark on how the bound behaves as the residual norm approaches zero would improve clarity.
[Numerical experiments] Numerical section: the tables report iteration counts and CPU times but lack standard deviation over the 50 runs; including error bars or min/max values would strengthen the empirical comparison.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful reading of our manuscript and the positive assessment that leads to a recommendation of minor revision. The referee's summary accurately captures the key contributions: the dual-space residual-based randomized extended Kaczmarz method (and its Nesterov variant) for inconsistent matrix equations AXB=C, the convergence analysis without full column rank assumptions, the explicit rate bounds, the feasible momentum interval, and the numerical improvements. As no specific major comments were raised in the report, we have no point-by-point rebuttals to provide. We will incorporate any minor suggestions during revision.

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained

full rationale

The paper's convergence analysis for the residual-based extended randomized Kaczmarz method and its Nesterov variant proceeds from the dual-space residual projection and the explicit contraction mapping on the expected error norm, using the randomized selection probabilities to bound the spectral radius factor strictly below one. Upper bounds on rates and the feasible momentum interval are obtained directly from these iteration rules without any reduction to fitted quantities, self-definitional loops, or load-bearing self-citations. The central theorems remain independent of the target results and do not rename known patterns or smuggle ansatzes via prior work.

Axiom & Free-Parameter Ledger

1 free parameters · 1 axioms · 0 invented entities

The central claims rest on standard probabilistic assumptions for randomized row selection and matrix norm properties typical in Kaczmarz analysis; the momentum parameter range is determined rather than freely fitted.

free parameters (1)

momentum parameter
A feasible range is derived; specific value within the range must be chosen for implementation.

axioms (1)

domain assumption Standard assumptions on randomized selection probabilities and matrix properties for convergence of extended Kaczmarz methods
Invoked to establish convergence without full column rank.

pith-pipeline@v0.9.0 · 5377 in / 1346 out tokens · 45640 ms · 2026-05-10T18:43:22.589476+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

17 extracted references · 17 canonical work pages

[1]

Hadjiantoni, S., Loizou, G.: Numerical strategies for recursive least squares solu- tions to the matrix equation AX = B. Int. J. Comput. Math.100, 497–510 (2023)

work page 2023
[2]

Hailin, Z.: An iterative algorithm to the least squares problem of AX = B over linear subspace. Math. Numer. Sin.45, 93–108 (2023)

work page 2023
[3]

Liu, X.: Hermitian and non-negative definite reflexive and anti-reflexive solutions to AX = B. Int. J. Comput. Math.95, 1666–1671 (2018)

work page 2018
[4]

Masoud, H.: Least squares solution of the linear operator equation. J. Optim. Theory Appl.170, 205–219 (2016)

work page 2016
[5]

Yuan, Y.: Least square solutions to the matrix equations AX = B and XC = D. Appl. Math. Comput.216, 3120–3125 (2010) 16

work page 2010
[6]

Masoud, H.: Least squares solution of the linear operator equation. Optim. Theory Appl.170, 205–219 (2016)

work page 2016
[7]

Wu, N.-C., Liu, C.-Z., Zuo, Q.: On the Kaczmarz methods based on relaxed greedy selection for solving matrixe quation AXB = C. J. Comput. Appl. Math. 413, 114374 (2022)

work page 2022
[8]

Wang, Y.-H., Song, Y.-Z.: An improved deterministic block Kaczmarz method for solving linear matrix equation AXB=C. J. Comput. Appl. Math.45(2) (2025) https://doi.org/10.1007/s40314-025-03426-1

work page doi:10.1007/s40314-025-03426-1 2025
[9]

Franklin Inst.359, 8991–9005 (2022)

Hafiei, S.G., Hajarian, M.: Developing Kaczmarz method for solving Sylvester matrix equations. Franklin Inst.359, 8991–9005 (2022)

work page 2022
[10]

Li, W.-G., Bao, W.-D., Xing, L.-L., Guo, Z.-W.: Kaczmarz-type methods for solving matrix equations. Int. J. Comput. Math.101, 708–731 (2024)

work page 2024
[11]

Ding, X.-J., Huang, B.-H.: The quaternion relaxed greedy randomized Kaczmarz method with adaptive parameters for solving quaternion matrix equation. Numer. Algorithms101, 1989–2016 (2025)

work page 1989
[12]

Gao, C.-X., Chen, F.: Accelerating convergence of randomized extended Kacz- marz methods with double-space residuals. J. Appl. Math. Comput.71(6), 8463–8477 (2025)

work page 2025
[13]

In: Proceedings of the 30th International Conference on Machine Learning, vol

Sutskever, I., Martens, J., Dahl, G., Hinton, G.E.: On the importance of initial- ization and momentum in deep learning. In: Proceedings of the 30th International Conference on Machine Learning, vol. 28, pp. 1139–1147. PMLR, Atlanta, Georgia, USA (2013).https://proceedings.mlr.press/v28/sutskever13.html

work page 2013
[14]

Yin, S.-S., Ouyang, Z.-G.: On constrained Kaczmarz algorithm with momentum for image reconstruction. Math. Methods Appl. Sci.47(7) (2024)

work page 2024
[15]

Bai, Z.-Z., Wang, L.: On convergence rates of Kaczmarz-type methods with different selection rules of working rows. Appl. Numer. Math.186, 289–319 (2023)

work page 2023
[16]

Loizou, N., Richt´ arik, P.: Momentum and stochastic momentum for stochas- tic gradient, Newton, proximal point and subspace descent methods. Comput. Optim. Appl.77, 653–710 (2020)

work page 2020
[17]

ACM Trans

Davis, T.A., Hu, Y.: The University of Florida Sparse Matrix Collection. ACM Trans. Math. Softw.38, 1–25 (2011) 17

work page 2011

[1] [1]

Hadjiantoni, S., Loizou, G.: Numerical strategies for recursive least squares solu- tions to the matrix equation AX = B. Int. J. Comput. Math.100, 497–510 (2023)

work page 2023

[2] [2]

Hailin, Z.: An iterative algorithm to the least squares problem of AX = B over linear subspace. Math. Numer. Sin.45, 93–108 (2023)

work page 2023

[3] [3]

Liu, X.: Hermitian and non-negative definite reflexive and anti-reflexive solutions to AX = B. Int. J. Comput. Math.95, 1666–1671 (2018)

work page 2018

[4] [4]

Masoud, H.: Least squares solution of the linear operator equation. J. Optim. Theory Appl.170, 205–219 (2016)

work page 2016

[5] [5]

Yuan, Y.: Least square solutions to the matrix equations AX = B and XC = D. Appl. Math. Comput.216, 3120–3125 (2010) 16

work page 2010

[6] [6]

Masoud, H.: Least squares solution of the linear operator equation. Optim. Theory Appl.170, 205–219 (2016)

work page 2016

[7] [7]

Wu, N.-C., Liu, C.-Z., Zuo, Q.: On the Kaczmarz methods based on relaxed greedy selection for solving matrixe quation AXB = C. J. Comput. Appl. Math. 413, 114374 (2022)

work page 2022

[8] [8]

Wang, Y.-H., Song, Y.-Z.: An improved deterministic block Kaczmarz method for solving linear matrix equation AXB=C. J. Comput. Appl. Math.45(2) (2025) https://doi.org/10.1007/s40314-025-03426-1

work page doi:10.1007/s40314-025-03426-1 2025

[9] [9]

Franklin Inst.359, 8991–9005 (2022)

Hafiei, S.G., Hajarian, M.: Developing Kaczmarz method for solving Sylvester matrix equations. Franklin Inst.359, 8991–9005 (2022)

work page 2022

[10] [10]

Li, W.-G., Bao, W.-D., Xing, L.-L., Guo, Z.-W.: Kaczmarz-type methods for solving matrix equations. Int. J. Comput. Math.101, 708–731 (2024)

work page 2024

[11] [11]

Ding, X.-J., Huang, B.-H.: The quaternion relaxed greedy randomized Kaczmarz method with adaptive parameters for solving quaternion matrix equation. Numer. Algorithms101, 1989–2016 (2025)

work page 1989

[12] [12]

Gao, C.-X., Chen, F.: Accelerating convergence of randomized extended Kacz- marz methods with double-space residuals. J. Appl. Math. Comput.71(6), 8463–8477 (2025)

work page 2025

[13] [13]

In: Proceedings of the 30th International Conference on Machine Learning, vol

Sutskever, I., Martens, J., Dahl, G., Hinton, G.E.: On the importance of initial- ization and momentum in deep learning. In: Proceedings of the 30th International Conference on Machine Learning, vol. 28, pp. 1139–1147. PMLR, Atlanta, Georgia, USA (2013).https://proceedings.mlr.press/v28/sutskever13.html

work page 2013

[14] [14]

Yin, S.-S., Ouyang, Z.-G.: On constrained Kaczmarz algorithm with momentum for image reconstruction. Math. Methods Appl. Sci.47(7) (2024)

work page 2024

[15] [15]

Bai, Z.-Z., Wang, L.: On convergence rates of Kaczmarz-type methods with different selection rules of working rows. Appl. Numer. Math.186, 289–319 (2023)

work page 2023

[16] [16]

Loizou, N., Richt´ arik, P.: Momentum and stochastic momentum for stochas- tic gradient, Newton, proximal point and subspace descent methods. Comput. Optim. Appl.77, 653–710 (2020)

work page 2020

[17] [17]

ACM Trans

Davis, T.A., Hu, Y.: The University of Florida Sparse Matrix Collection. ACM Trans. Math. Softw.38, 1–25 (2011) 17

work page 2011