大型稀疏线性系统的一类含参数的贪心随机Kaczmarz算法

doi:10.12066/j.issn.1007-2861.2151

Journal of Shanghai University（Natural Science Edition） ›› 2020, Vol. 26 ›› Issue (6): 1026-1034.doi: 10.12066/j.issn.1007-2861.2151

• Research Articles • Previous Articles

Parametric greedy randomized Kaczmarz algorithm for solving large sparse linear systems

LIU Yong¹^,²(), $\fbox{GU Chuanqing}$ ², CUI Rongrong³

1. Changzhou College of Information Technology, Changzhou 213164, Jiangsu, China
2. College of Sciences, Shanghai University, Shanghai 200444, China
3. School of Mathematics and Statistics, Yancheng Teachers University, Yancheng 224002, Jiangsu, China

Received:2019-03-04 Online:2020-12-31 Published:2020-12-29
Contact: LIU Yong E-mail:lyccit@yeah.net

Abstract

Abstract:

To solve large sparse linear systems, a relaxation parameter in introduced in the involved iterative formula of greedy randomized Kaczmarz (GRK) algorithm, and obtain a parametric greedy randomizedKaczmarzalgorithm is obtained. The convergence of this algorithm is proved when the linear system is consistent, and it is showed that it can be more efficient than the greedy randomized Kaczmarz algorithm if the relaxation parameter is chosen appropriately.

Key words: large sparse linear system, greedy randomized Kaczmarz (GRK) algorithm, relaxation parameter

CLC Number:

O241.6

LIU Yong, $\fbox{GU Chuanqing}$ , CUI Rongrong. Parametric greedy randomized Kaczmarz algorithm for solving large sparse linear systems[J]. Journal of Shanghai University（Natural Science Edition）, 2020, 26(6): 1026-1034.

Figures/Tables 3

References 12

[1]	Kaczmarz S. Angenäherte auflösung von systemen linearer gleichungen[J]. Bull Int Acad Polon Sci Lett A, 1937,35:355-357.
[2]	Herman G T, Meyer L B. Algebraic reconstruction techniques can be made computationally efficient[J]. IEEE Transactions on Medical Imaging, 1993,12(3):600-609. doi: 10.1109/42.241889 pmid: 18218454
[3]	Popa C, Zdunek R. Kaczmarz extended algorithm for tomographic image reconstruction from limited-data[J]. Mathematics and Computers in Simulation, 2004,65(6):579-598. doi: 10.1016/j.matcom.2004.01.021
[4]	Gordon R, Bender R, Herman G T. Algebraic reconstruction techniques (ART) for three-dimensional electron microscopy and X-ray photography[J]. Journal of Theoretical Biology, 1970,29(3):471-481. doi: 10.1016/0022-5193(70)90109-8 pmid: 5492997
[5]	Byrne C. A unified treatment of some iterative algorithms in signal processing and image reconstruction[J]. Inverse Problems, 2004,20(1):103-120. doi: 10.1088/0266-5611/20/1/006
[6]	Pasqualetti F, Carli R, Bullo F. Distributed estimation via iterative projections with application to power network monitoring[J]. Automatica, 2012,48(5):747-758. doi: 10.1016/j.automatica.2012.02.025
[7]	Bai Z Z, Liu X G. On the Meany inequality with applications to convergence analysis of several row-action iteration methods[J]. Numerische Mathematik, 2013,124(2):215-236. doi: 10.1007/s00211-012-0512-6
[8]	Bai Z Z, Wu W T. On convergence rate of the randomized Kaczmarz method[J]. Linear Algebra and its Applications, 2018,553(15):252-269. doi: 10.1016/j.laa.2018.05.009
[9]	Strohmer T, Vershynin R. A randomized Kaczmarz algorithm with exponential conver-gence[J]. Journal of Fourier Analysis and Applications, 2009,15(2):262-278. doi: 10.1007/s00041-008-9030-4
[10]	Zouzias A, Freris N M. Randomized extended Kaczmarz for solving least squares[J]. SIAM Journal on Matrix Analysis and Applications, 2013,34(2):773-793. doi: 10.1137/120889897
[11]	Bai Z Z, Wu W T. On greedy randomized Kaczmarz method for solving large sparse linear systems[J]. SIAM Journal on Scientific Computing, 2018,40(1):592-606.
[12]	Davis T A, Hu Y. The university of Florida sparse matrix collection[J]. ACM Transactions on Mathematical Software, 2011,38(1):1-25.

Parametric greedy randomized Kaczmarz algorithm for solving large sparse linear systems

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 3

References 12

Related Articles 0

Recommended Articles

Metrics

Comments