A partially block randomized extended Kaczmarz method for solving large overdetermined inconsistent linear systems

Feng Yin; Bu-Yue Zhang; Guang-Xin Huang; Feng Yin; Bu-Yue Zhang; Guang-Xin Huang

doi:10.3934/math.2023941

AIMS Mathematics

2023, Volume 8, Issue 8: 18512-18527. doi: 10.3934/math.2023941

Previous Article Next Article

Research article Special Issues

A partially block randomized extended Kaczmarz method for solving large overdetermined inconsistent linear systems

1.
College of Mathematical and Physics, Chengdu University of Technology, Chengdu 610059, China
2.
College of Computer Science and Cyber Security, Chengdu University of Technology, Chengdu 610059, China
3.
Sichuan Geomathematics Key Laboratory, Chengdu University of Technology, Chengdu 610059, China

Received: 22 December 2022 Revised: 08 May 2023 Accepted: 15 May 2023 Published: 31 May 2023
MSC : 65F10, 65F20

This paper presents a partial block randomized extended Kaczmarz (PBREK) method for solving large overdetermined inconsistent linear system of equations $ Ax = b $. The convergence theorem of the PBREK method is derived. Several examples are given to illustrate the effectiveness of the proposed PBREK method compared with the prevuious PREK method and the randomized extended Kaczmarz (REK) method.
- partial block randomized extended Kaczmarz,
- overdetermined inconsistent systems,
- matrix paving,
- Kaczmarz method
Citation: Feng Yin, Bu-Yue Zhang, Guang-Xin Huang. A partially block randomized extended Kaczmarz method for solving large overdetermined inconsistent linear systems[J]. AIMS Mathematics, 2023, 8(8): 18512-18527. doi: 10.3934/math.2023941

Related Papers:

Abstract

This paper presents a partial block randomized extended Kaczmarz (PBREK) method for solving large overdetermined inconsistent linear system of equations $ Ax = b $. The convergence theorem of the PBREK method is derived. Several examples are given to illustrate the effectiveness of the proposed PBREK method compared with the prevuious PREK method and the randomized extended Kaczmarz (REK) method.

References

[1]	Z. Z. Bai, W. T. Wu, On partially randomized extended Kaczmarz method for solving large sparse overdetermined inconsistent linear systems, Linear Algebra Appl., 578 (2019), 225–250. https://doi.org/10.1016/j.laa.2019.05.005 doi: 10.1016/j.laa.2019.05.005
[2]	B. Dumitrescu, On the relation between the randomized extended Kaczmarz algorithm and coordinate descent, BIT Numer. Math., 55 (2015), 1005–1015. https://doi.org/10.1007/s10543-014-0526-9 doi: 10.1007/s10543-014-0526-9
[3]	K. Du, W. T. Si, X. H. Sun, Randomized extended average block Kaczmarz for solving least squares, SIAM J. Sci. Comput., 42 (2020), A3541–A3559. https://doi.org/10.1137/20M1312629 doi: 10.1137/20M1312629
[4]	P. P. B. Eggermont, G. T. Herman, A. Lent, Iterative algorithms for large partitioned linear systems, with applications to image reconstruction, Linear Algebra Appl., 40 (1981), 37–67. http://doi.org/10.1016/0024-3795(81)90139-7 doi: 10.1016/0024-3795(81)90139-7
[5]	T. Elfving, Block-iterative methods for consistent and inconsistent linear equations, Numer. Math., 35 (1980), 1–12. http://doi.org/10.1007/BF01396365 doi: 10.1007/BF01396365
[6]	S. G. Shafiei, M. Hajarian, Developing Kaczmarz method for solving Sylvester matrix equations, J. Franklin I., 359 (2022), 8991–9005. https://doi.org/10.1016/j.jfranklin.2022.09.028 doi: 10.1016/j.jfranklin.2022.09.028
[7]	S. Kaczmarz, Angenaherte auflosung von systemen linearer glei-chungen, Bull. Int. Acad. Pol. Sci. Lett. A, 35 (1937), 335–357
[8]	J. Liu, S. J. Wright, An accelerated randomized Kaczmarz algorithm, Math. Comput., 85 (2016), 153-178. https://doi.org/10.1090/mcom/2971 doi: 10.1090/mcom/2971
[9]	D. Needell, J. A. Tropp, Paved with good intentions: analysis of a randomized block Kaczmarz method, Linear Algebra Appl., 441 (2014), 199–221. https://doi.org/10.1016/j.laa.2012.12.022 doi: 10.1016/j.laa.2012.12.022
[10]	D. Needell, R. Zhao, A. Zouzias, Randomized block Kaczmarz method with projection for solving least squares, Linear Algebra Appl., 484 (2015), 322–343. https://doi.org/10.1016/j.laa.2015.06.027 doi: 10.1016/j.laa.2015.06.027
[11]	I. Necoara, Faster randomized block Kaczmarz algorithms, SIAM J. Matrix Anal. Appl., 40 (2019), 1425–1452. https://doi.org/10.1137/19M1251643 doi: 10.1137/19M1251643
[12]	S. Petra, C. Popa, Single projection Kaczmarz extended algorithms, Numer. Algorithms, 73 (2016), 791–806. https://doi.org/10.1007/s11075-016-0118-7 doi: 10.1007/s11075-016-0118-7
[13]	T. Strohmer, R.Vershynin, A randomized Kaczmarz algorithm with exponential convergence, J. Fourier Anal. Appl., 15 (2009), 262–278. https://doi.org/10.1007/s00041-008-9030-4 doi: 10.1007/s00041-008-9030-4
[14]	N. C. Wu, H. Xiang, Projected randomized Kaczmarz methods, J. Comput. Appl. Math., 372 (2020), 112672. https://doi.org/10.1016/j.cam.2019.112672 doi: 10.1016/j.cam.2019.112672
[15]	A. Zouzias, N. M. Freris, Randomized extended Kaczmarz for solving least squares, SIAM J. Matrix Anal. Appl., 34 (2013), 773–793. https://doi.org/10.1137/120889897 doi: 10.1137/120889897

Reader Comments

Your name:*

Email:*
© 2023 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)