中文

Journal of Shanghai University >

2020 , Vol. 26 >Issue 6: 1026 - 1034

DOI: https://doi.org/10.12066/j.issn.1007-2861.2151

Research Articles

Parametric greedy randomized Kaczmarz algorithm for solving large sparse linear systems

Expand
  • 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 date: 2019-03-04

  Online published: 2019-04-28

Fold

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

Cite this article

LIU Yong, $\fbox{GU Chuanqing}$ , CUI Rongrong . Parametric greedy randomized Kaczmarz algorithm for solving large sparse linear systems[J]. Journal of Shanghai University, 2020 , 26(6) : 1026 -1034 . DOI: 10.12066/j.issn.1007-2861.2151

References

[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.
[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.
[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.
[5] Byrne C. A unified treatment of some iterative algorithms in signal processing and image reconstruction[J]. Inverse Problems, 2004,20(1):103-120.
[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.
[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.
[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.
[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.
[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.
[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.
Options
Outlines

/

〈 〉