Greedy Randomized-Distance Kaczmarz Method for Solving Large Sparse Linear Systems

被引：0

作者：

Du Y. ^{[1
]}

Yin J. ^{[1
]}

Zhang K. ^{[2
]}

机构：

[1] School of Mathematical Sciences, Tongji University, Shanghai

[2] College of Arts and Sciences, Shanghai Maritime University, Shanghai

来源：

Tongji Daxue Xuebao/Journal of Tongji University | 2020年 / 48卷 / 08期

关键词：

Convergence property; Kaczmarz method; Randomized iteration; Sparse linear systems;

D O I：

10.11908/j.issn.0253-374x.20041

中图分类号：

学科分类号：

摘要：

Based on a new probability criterion to select the working rows from the coefficient matrix, a greedy-distance randomized Kaczmarz method was proposed to solve large sparse linear systems. The theoretical analysis demonstrates that this method converges to the least-norm solution when the linear system is consistent, and the convergence factor of the greedy-distance randomized Kaczmarz method is smaller than that of the randomized Kaczmarz method. Moreover, the numerical results have verified its effectiveness. © 2020, Editorial Department of Journal of Tongji University. All right reserved.

引用

页码：1224 / 1231and1240

共 31 条

[21]

STROHMER T, VERSHYNIN R., A randomized Kaczmarz algorithm with exponential convergence, Journal of Fourier Analysis and Applications, 15, (2009)

[22]

BAI Z Z, WU W T., On greedy randomized Kaczmarz method for solving large sparse linear systems, SIAM Journal on Scientific Computing, 40, (2018)

[23]

BAI Z Z, WU W T., On relaxed greedy randomized Kaczmarz methods for solving large sparse linear systems, Applied Mathematics Letters, 83, (2018)

[24]

BAI Z Z, WU W T., On partially randomized extended Kaczmarz method for solving large sparse overdetermined inconsistent linear systems, Linear Algebra and its Applications, 578, (2019)

[25]

POPA C., Convergence rates for Kaczmarz-type algorithms, Numerical Algorithms, 79, (2018)

[26]

BAI Z Z, WU W T., On convergence rate of the randomized Kaczmarz method, Linear Algebra and its Applications, 553, (2018)

[27]

BAI Z Z, WU W T., On greedy randomized coordinate descent methods for solving large linear least-squares problems, Numerical Linear Algebra with Applications, 26, (2019)

[28]

LEVENTHAL D, LEWIS A S., Randomized methods for linear constraints: convergence rates and conditioning, Mathematics of Operations Research, 35, (2010)

[29]

NUTINI J, SEPEHRY B, LARADJI I, Et al., Convergence rates for greedy Kaczmarz algorithms, and faster randomized Kaczmarz rules using the orthogonality graph, (2016)

[30]

HOLODNAK J T, IPSEN I C F., Randomized approximation of the gram matrix: Exact computation and probabilistic bounds, SIAM Journal on Matrix Analysis and Applications, 36, (2015)

← 1 2 3 4 →