Communications on Applied Mathematics and Computation >

2025 , Vol. 7 >Issue 5: 2120 - 2136

DOI: https://doi.org/10.1007/s42967-024-00447-1

ORIGINAL PAPERS

A Semi-randomized Block Kaczmarz Method with Simple Random Sampling for Large-Scale Consistent Linear Systems

  • Gang Wu ,
  • Qiao Chang
Expand
  • 1. Key Laboratory of Data Science and Smart Education, Ministry of Education, Hainan Normal University, Haikou, 571158,, Hainan, China;
    2. School of Mathematics, China University of Mining and Technology, Xuzhou, 221116, Jiangsu, China;
    3. School of Big Data, Fuzhou University of International Studies and Trade, Fuzhou, 350202, Fujian, China

Received date: 2023-11-30

  Revised date: 2024-07-08

  Accepted date: 2024-07-13

  Online published: 2024-11-22

Supported by

This work is supported by the National Natural Science Foundation of China under grant 12271518, the Fujian Natural Science Foundation under grant 2023J01354, the Key Research and Development Project of Xuzhou Natural Science Foundation under grant KC22288, and the Open Project of Key Laboratory of Data Science and Intelligence Education of the Ministry of Education under grant DSIE202203.

Fold

Abstract

The randomized block Kaczmarz (RBK) method is a randomized orthogonal projection iterative approach, which plays an important role in solving large-scale linear systems. A key point of this type of method is to select working rows effectively during iterations. However, in most of the RBK-type methods, one has to scan all the rows of the coefficient matrix in advance to compute probabilities or paving, or to compute the residual vector of the linear system in each iteration to determine the working rows. These are unfavorable for big data problems. To cure these drawbacks, we propose a semi-randomized block Kaczmarz (SRBK) method with simple random sampling for large-scale linear systems in this paper. The convergence of the proposed method is established. Numerical experiments on some real-world and large-scale data sets show that the proposed method is often superior to many state-of-the-art RBK-type methods for large linear systems.

Key words： Randomized Kaczmarz (RK) method; Randomized block Kaczmarz (RBK) method; Semi-randomized Kaczmarz (SRK) method; Semi-randomized block Kaczmarz (SRBK) method; Simple random sampling; Large-scale linear system

Cite this article

Gang Wu , Qiao Chang . A Semi-randomized Block Kaczmarz Method with Simple Random Sampling for Large-Scale Consistent Linear Systems[J]. Communications on Applied Mathematics and Computation, 2025 , 7(5) : 2120 -2136 . DOI: 10.1007/s42967-024-00447-1

References

[1] Agaskar A., Wang C., Lu Y.-M.: Randomized Kaczmarz algorithms: exact MSE analysis and optimal sampling probabilities. In: IEEE Global Conference on Signal and Information Processing, Atlanta, GA, pp. 389-393 (2014)
[2] Ansorge, R.: Connections between the Cimmino-method and the Kaczmarz-method for the solution of singular and regular systems of equations. Computing 33, 367-375 (1984)
[3] Bai, Z.-Z., Pan, J.-Y.: Matrix Analysis and Computations. SIAM, Philadelphia (2021)
[4] 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)
[5] Bai, Z.-Z., Wang, L., Muratova, G.V.: On relaxed greedy randomized augmented Kaczmarz methods for solving large sparse inconsistent linear systems. East Asian J. Appl. Math. 27, 323-332 (2021)
[6] Bai, Z.-Z., Wang, L., Wu, W.-T.: On convergence rate of the randomized Gauss-Seidel method. Linear Algebra Appl. 611, 237-252 (2021)
[7] 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)
[8] Bai, Z.-Z., Wu, W.-T.: On convergence rate of the randomized Kaczmarz method. Linear Algebra Appl. 553, 252-269 (2018)
[9] 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)
[10] 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)
[11] Bai, Z.-Z., Wu, W.-T.: On greedy randomized coordinate descent methods for solving large linear least-squares problems. Numer. Linear Algebra Appl. 26, e2237 (2019)
[12] 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)
[13] Bai, Z.-Z., Wu, W.-T.: Randomized Kaczmarz iteration methods: algorithmic extensions and convergence theory. Jpn. J. Ind. Appl. Math. 40, 1421-1443 (2023)
[14] Carlton, M.: Probability and statistics for computer scientists. Am. Stat. 62, 271-272 (2008)
[15] Chen, J.-Q., Huang, Z.-D.: On the error estimate of the randomized double block Kaczmarz method. Appl. Math. Comput. 370, 124907 (2020)
[16] Clough, R.W., Penzien, J.: Structural Dynamics. McGrowHill Inc, New York (1975)
[17] Davis, T., Hu, Y.: The University of Florida sparse matrix collection. ACM Trans. Math. Softw. 38, 1-25 (2011)
[18] Du, K., Si, W.-T., Sun, X.-H.: Randomized extended average block Kaczmarz for solving least squares. SIAM J. Sci. Comput. 42, A3541-A3559 (2020)
[19] Elfving, T.: Block-iterative methods for consistent and inconsistent linear equations. Numer. Math. 35, 1-12 (1980)
[20] Freund, R.W.: Krylov-subspace methods for reduced-order modeling in circuit simulation. J. Comput. Appl. Math. 123, 395-421 (2000)
[21] Golub, G.H., Van Loan, C.F.: Matrix Computations. 4th edn. The Johns Hopkins University Press, Baltimore (2013)
[22] Gordon, R., Bender, R., Herman, G.: Algebraic reconstruction techniques (ART) for three-dimensional electron microscopy and X-ray photography. J. Theor. Biol. 29, 471-481 (1970)
[23] Guo, W., Chen, H., Geng, W., Lei, L.: A modified Kaczmarz algorithm for computerized tomographic image reconstruction. IEEE Intern. Conf. Biom. Eng. Inf. 3, 1-4 (2009)
[24] Jiang, Y., Wu, G., Jiang, L.: A semi-randomized Kaczmarz method with simple random sampling for large-scale linear systems. Adv. Comput. Math. 49, 20 (2023)
[25] Kaczmarz, S.: Approximate solution of systems of linear equations. Int. J. Control 35, 355-357 (1937)
[26] Lee, S., Kim, H.: Noise properties of reconstructed images in a kilo-voltage on-board imaging system with iterative reconstruction techniques: a phantom study. Phys. Med. 30, 365-373 (2014)
[27] Leventhal, D., Lewis, A.: Randomized methods for linear constraints: convergence rates and conditioning. Math. Oper. Res. 35, 641-654 (2010)
[28] Liu, Y., Gu, C.: On greedy randomized block Kaczmarz method for consistent linear systems. Linear Algebra Appl. 616, 178-200 (2021)
[29] Ma, A., Needell, D., Ramdas, A.: Convergence properties of the randomized extended Gauss-Seidel and Kaczmarz methods. SIAM J. Matrix Anal. Appl. 36, 1590-1604 (2015)
[30] Miao, C.-Q., Wu, W.-T.: On greedy randomized average block Kaczmarz method for solving large linear systems. J. Comput. Appl. Math. 413, 114372 (2022)
[31] Necoara, I.: Faster randomized block Kaczmarz algorithms. SIAM J. Matrix Anal. Appl. 40, 1425-1452 (2019)
[32] Needell, D., Tropp, J.: Paved with good intentions: analysis of a randomized block Kaczmarz method. Linear Algebra Appl. 441, 199-221 (2014)
[33] Needell, D., Zhao, R., Zouzias, A.: Randomized block Kaczmarz method with projection for solving least squares. Linear Algebra Appl. 484, 322-343 (2015)
[34] Niu, Y., Zheng, B.: A greedy block Kaczmarz algorithm for solving large-scale linear systems. Appl. Math. Letters. 104, 106294 (2020)
[35] Popa, C., Zdunek, R.: Kaczmarz extended algorithm for tomographic image reconstruction from limited-data. Math. Comput. 65, 579-598 (2004)
[36] Saad, Y.: Iterative Methods for Sparse Linear Systems, vol. 82. SIAM, Philadelphia (2003)
[37] Sakurai, T., Tadano, H., Kuramashi, Y.: Application of block Krylov subspace algorithms to the Wilson-Dirac equation with multiple right-hand sides in lattice QCD. Comput. Phys. Commun. 181, 113-117 (2010)
[38] Soudais, P.: Iterative solution of a 3D scattering problem from arbitrary shaped multidielectric and multiconducting bodies. IEEE Trans. Antennas Propag. 42, 954-959 (1994)
[39] Steinerberger, S.: A weighted randomized Kaczmarz method for solving linear systems. Math. Comput. 90, 2815-2826 (2021)
[40] Strohmer, T., Vershynin, R.: A randomized Kaczmarz algorithm with exponential convergence. J. Fourier Anal. Appl. 15, 262-278 (2009)
[41] Tajaddini, A., Wu, G., Saberi-Movahed, F., Azizizadeh, N.: Two new variants of the simpler block GMRES method with vector deflation and eigenvalue deflation for multiple linear systems. J. Sci. Comput. 86, 9 (2021)
[42] Zhang, J.: A new greedy Kaczmarz algorithm for the solution of very large linear systems. Appl. Math. Lett. 91, 207-212 (2019)
[43] Zhang, J., Guo, J.: On relaxed greedy randomized coordinate descent methods for solving large linear least-squares problems. Appl. Numer. Math. 157, 372-384 (2020)
[44] Zouzias, A., Freris, N.: Randomized extended Kaczmarz for solving least-squares. SIAM J. Matrix Anal. Appl. 34, 773-793 (2012)
Options
Outlines

/

〈 〉

Copyright © Editorial By Communications on Applied Mathematics and Computation
沪ICP备09014157