ORIGINAL PAPERS

On Multi-step Partially Randomized Extended Kaczmarz Method for Solving Large Sparse Inconsistent Linear Systems

  • Jin-Feng Mao ,
  • Fang Chen
Expand
  • School of Applied Science, Beijing Information Science and Technology University, Beijing, 100192, China

Received date: 2023-11-27

  Revised date: 2024-02-08

  Accepted date: 2024-02-10

  Online published: 2024-05-20

Supported by

Supported by the R &D Program of Beijing Municipal Education Commission, China (Grant No. KM202011232019).

Abstract

To enhance the computational performance of the partially randomized extended Kaczmarz (PREK) method, we propose the multi-step PREK (MPREK) method. By iteratively updating at each step, we establish a non-smooth inner-outer iteration scheme to solve the large, sparse, and inconsistent linear systems. For the MPREK method, a proof of its convergence and an upper bound on the convergence rate are given. Moreover, we show that this upper bound can be lower than that of the PREK method and the multi-step randomized extended Kaczmarz (MREK) method for certain typical choices of the inner iteration step size. Numerical experiments also indicate that, for an appropriate choice of the number of inner iteration steps, the MPREK method has a more efficient computational performance.

Cite this article

Jin-Feng Mao , Fang Chen . On Multi-step Partially Randomized Extended Kaczmarz Method for Solving Large Sparse Inconsistent Linear Systems[J]. Communications on Applied Mathematics and Computation, 2025 , 7(5) : 1724 -1743 . DOI: 10.1007/s42967-024-00385-y

References

[1] Bai, Z.-Z.: Several splittings for non-Hermitian linear systems. Sci. China Ser. A Math. 51, 1339-1348 (2008)
[2] Bai, Z.-Z., Pan, J.-Y.: Matrix Analysis and Computations. SIAM, Philadelphia (2021)
[3] Bai, Z.-Z., Wang, L.: On multi-step randomized extended Kaczmarz method for solving large sparse inconsistent linear systems. Appl. Numer. Math. 192, 197-213 (2023)
[4] Bai, Z.-Z., Wu, W.-T.: On convergence rate of the randomized Kaczmarz method. Linear Algebra Appl. 553, 252-269 (2018)
[5] Bai, Z.-Z., Wu, W.-T.: On greedy randomized Kaczmarz method for solving large sparse linear systems. SIAM J. Sci. Comput. 40, A592-A606 (2018)
[6] Bai, Z.-Z., Wu, W.-T.: On relaxed greedy randomized Kaczmarz methods for solving large sparse linear systems. Appl. Math. Lett. 83, 21-26 (2018)
[7] Bai, Z.-Z., Wu, W.-T.: On partially randomized extended Kaczmarz method for solving large sparse overdetermined inconsistent linear systems. Linear Algebra Appl. 578, 225-250 (2019)
[8] Bai, Z.-Z., Wu, W.-T.: On greedy randomized augmented Kaczmarz method for solving large sparse inconsistent linear systems. SIAM J. Sci. Comput. 43, A3892-A3911 (2021)
[9] Bai, Z.-Z., Wu, W.-T.: Randomized Kaczmarz iteration methods: algorithmic extensions and convergence theory. Jpn. J. Ind. Appl. Math. 40, 1421-1443 (2023)
[10] Byrne, C.: A unifed treatment of some iterative algorithms in signal processing and image re-construction. Inverse Prob. 20, 103-120 (2003)
[11] Censor, Y.: Row-action methods for huge and sparse systems and their applications. SIAM Rev. 23, 444-466 (1981)
[12] Censor, Y.: Parallel application of block-iterative methods in medical imaging and radiation therapy. Math. Program. 42, 307-325 (1988)
[13] Du, K.: Tight upper bounds for the convergence of the randomized extended Kaczmarz and Gauss-Seidel algorithms. Numer. Linear Algebra Appl. 26, e2233 (2019)
[14] Eggermont, P.P.B., Herman, G.T., Lent, A.: Iterative algorithms for large partitioned linear systems, with applications to image reconstruction. Linear Algebra Appl. 40, 37-67 (1981)
[15] Eldar, Y.C., Needell, D.: Acceleration of randomized Kaczmarz methods via the Johnson-Lindenstrauss lemma. Numer. Algorithms 58, 163-177 (2011)
[16] Feichtinger, H.G., Cenker, C., Mayer, M., Steier, H., Strohmer, T.: New variants of the POCS method using affine subspaces of finite codimension with applications to irregular sampling. Vis. Commun. Image Process. 1992, 299-310 (1818)
[17] Gordon, R., Bender, R., Herman, G.T.: Algebraic reconstruction techniques (ART) for three-dimensional electron microscopy and X-ray photography. J. Theor. Biol. 29, 471-481 (1970)
[18] Guenther, R.B., Kerber, C.W., Killian, E.K., Smith, K.T., Wagner, S.L.: Reconstruction of objects from radiographs and the location of brain tumors. Proc. Natl. Acad. Sci. 71, 4884-4886 (1974)
[19] Herman, G.T.: Fundamentals of Computerized Tomography: Image Reconstruction from Projections. Springer, Berlin (2009)
[20] Herman, G.T., Davidi, R.: Image reconstruction from a small number of projections. Inverse Prob. 24, 045011 (2008)
[21] Kaczmarz, S.: Angenäherte auflösung von systemen linearer gleichungen. Bull. Int. Acad. Polon. Sci. Lett. 35, 355-357 (1937)
[22] Kak, A.C., Slaney, M.: Principles of Computerized Tomographic Imaging. SIAM, Philadelphia, PA (2001)
[23] Leventhal, D., Lewis, A.S.: Randomized methods for linear constraints: convergence rates and conditioning. Math. Oper. Res. 35, 641-654 (2010)
[24] Liu, Y., Gu, C.-Q.: Variant of greedy randomized Kaczmarz for ridge regression. Appl. Numer. Math. 143, 223-246 (2019)
[25] Needell, D.: Randomized Kaczmarz solver for noisy linear systems. BIT Numer. Math. 50, 395-403 (2010)
[26] Needell, D., Zhao, R., Zouzias, A.: Randomized block Kaczmarz method with projection for solving least squares. Linear Algebra Appl. 484, 322-343 (2015)
[27] Popa, C.: Least-squares solution of overdetermined inconsistent linear systems using Kaczmarz’s relaxation. Int. J. Comput. Math. 55, 79-89 (1995)
[28] Popa, C.: Extensions of block-projections methods with relaxation parameters to inconsistent and rank-deficient least-squares problems. BIT 38, 151-176 (1998)
[29] Popa, C., Zdunek, R.: Kaczmarz extended algorithm for tomographic image reconstruction from limited data. Math. Comput. Simul. 65, 579-598 (2004)
[30] Strohmer, T., Vershynin, R.: A randomized Kaczmarz algorithm with exponential convergence. J. Fourier Anal. Appl. 15, 262-278 (2009)
[31] Zhang, J.-J.: A new greedy Kaczmarz algorithm for the solution of very large linear systems. Appl. Math. Lett. 91, 207-212 (2019)
[32] Zouzias, A., Freris, N.M.: Randomized extended Kaczmarz for solving least squares. SIAM J. Matrix Anal. Appl. 34, 773-793 (2013)
Options
Outlines

/