Two Novel Randomized Kaczmarz Methods with Maximal Residual for Consistent Linear Systems

Abstract

Inspired by Randomized Kaczmarz with Mismatched Adjoint (RKMA) proposed by Lorenz et al. [17] and the semi-randomized Kaczmarz method with simple random sampling (PRKS) proposed by Jiang et al. [12], we propose two novel randomized Kaczmarz (RK) methods with maximal residual for solving large overdetermined consistent linear systems. In the new methods, we select the row with the optimal local residuals as the working row, and, respectively, project the current solution orthogonally or obliquely onto the hyperplane formed by the working row. Under the assumption that matrix A has full column rank, we conduct a convergence analysis of the new RK methods and derive the upper bounds for their expected convergence rates. Furthermore, numerical experiments are performed to validate the superior efficiency of these methods compared to the RK, RKMA, PRKS, and the fast deterministic block Kaczmarz methods.

Keywords

Kaczmarz method / Maximal residual / Oblique projection / Simple random sampling / Large overdetermined linear systems / 65F10 / 68W20

References

[1] Bai Z-Z, Wu W-T. On greedy randomized Kaczmarz method for solving large sparse linear systems. SIAM J. Sci. Comput., 2018, 40(1): 592-606

[2] Bai Z-Z, Wu W-T. On relaxed greedy randomized Kaczmarz methods for solving large sparse linear systems. Appl. Math. Lett., 2018, 83: 21-26

[3] Byrne C. A unified treatment of some iterative algorithms in signal processing and image reconstruction. Inverse Prob., 2004, 20(1): 103-120

[4] Censor Y, Zenios SA. Parallel Optimization: Theory, Algorithms, and Applications, 1997, New York. Numerical Mathematics and Scientific Computation. Oxford University Press

[5] Chen J-Q, Huang Z-D. On a fast deterministic block Kaczmarz method for solving large-scale linear systems. Numer. Algor., 2022, 89(3): 1007-1029

[6] Davis TA, Hu Y. The university of Florida sparse matrix collection. ACM Trans. Math. Softw., 2011, 38(1): 1-25

[7] Eggermont PPB, Herman GT, Lent A. Iterative algorithms for large partitioned linear systems, with applications to image reconstruction. Linear Algebra Appl., 1981, 40: 37-67

[8] Golub, G.H., Van Loan, C.F.: Matrix Computations, 4th ed. Johns Hopkins Studies in the Mathematical Sciences. The Johns Hopkins University Press, Baltimore (2013)

[9] Hansen PC, Saxild-Hansen M. AIR tools—a MATLAB package of algebraic iterative reconstruction methods. J. Comput. Appl. Math., 2012, 236(8): 2167-2178

[10] Herman, G.T.: Fundamentals of Computerized Tomography. Advances in Pattern Recognition. Springer, London (2009). https://doi.org/10.1007/978-1-84628-723-7

[11] Huang Y, Huang J, Liu J, Yan M, Dong Y, Lv J, Chen C, Chen S. WaveDM: wavelet-based diffusion models for image restoration. IEEE Trans. Multimedia, 2024, 26: 7058-7073

[12] Jiang Y, Wu G, Jiang L. A semi-randomized Kaczmarz method with simple random sampling for large-scale linear systems. Adv. Comput. Math., 2023, 49(2): 20

[13] Kaczmarz, S.: Angenäherte auflösung von systemen linearer Gleichungen. Bull. Int. Acad. Sci. Pologne, A 35, 355–357 (1937)

[14] Leventhal D, Lewis AS. Randomized methods for linear equations and data fitting. Linear Algebra Appl., 2010, 432(9): 2282-2289

[15] Li, W.-G., Xing, L.-L., Bao, W.-D., Qiao, T.-T.: Kaczmarz-type Methods for Solving Linear and Nonlinear Equations. Sinopec Press Ltd., Beijing (2022)

[16] Liu L, Li W-G, Bao W-D, Xing L-L. Greedy Kaczmarz methods for nonlinear equation. J. Comput. Appl. Math., 2025, 467 116630

[17] Lorenz DA, Rose S, Schöpfer F. The randomized Kaczmarz method with mismatched adjoint. BIT Numer. Math., 2018, 58(4): 1079-1098

[18] Needell D, Tropp JA. Paved with good intentions: analysis of a randomized block Kaczmarz method. Linear Algebra Appl., 2014, 441: 199-221

[19] Richtárik P, Takáč M. Stochastic reformulations of linear systems: algorithms and convergence theory. SIAM J. Matrix Anal. Appl., 2020, 41(2): 487-524

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

[21] Trefethen, L.N.: Numerical Linear Algebra. SIAM, Philadelphia, PA (1997)

RIGHTS & PERMISSIONS

Shanghai University