Randomized Kaczmarz iteration methods: Algorithmic extensions and convergence theory

被引：26

作者：

Bai, Zhong-Zhi ^{[1
,2
]}

Wu, Wen-Ting ^{[3
]}

机构：

[1] Chinese Acad Sci, Inst Computat Math & Sci Engn Comp, Acad Math & Syst Sci, State Key Lab Sci Engn Comp, POB 2719, Beijing 100190, Peoples R China

[2] Univ Chinese Acad Sci, Sch Math Sci, Beijing 100049, Peoples R China

[3] Beijing Inst Technol, Sch Math & Stat, Beijing 100081, Peoples R China

来源：

JAPAN JOURNAL OF INDUSTRIAL AND APPLIED MATHEMATICS | 2023年 / 40卷 / 03期

基金：

中国国家自然科学基金;

关键词：

System of linear equations; Randomized projection iteration; Kaczmarz method; Coordinate descent method; Convergence property; EXTENDED KACZMARZ; GAUSS-SEIDEL; RATES;

D O I：

10.1007/s13160-023-00586-7

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We review and compare several representative and effective randomized projection iteration methods, including the randomized Kaczmarz method, the randomized coordinate descent method, and their modifications and extensions, for solving the large, sparse, consistent or inconsistent systems of linear equations. We also anatomize, extract, and purify the asymptotic convergence theories of these iteration methods, and discuss, analyze, and summarize their advantages and disadvantages from the viewpoints of both theory and computations.

引用

页码：1421 / 1443

页数：23

共 26 条

[1]

[Anonymous], 2001, The Mathematics of Computerized Tomography

[2]

Bai Z-Z., 2021, Matrix Analysis and Computations, DOI [10.1137/1.9781611976632, DOI 10.1137/1.9781611976632]

[3] On convergence rates of Kaczmarz-type methods with different selection rules of working rows [J].

Bai, Zhong-Zhi ;

Wang, Lu .

APPLIED NUMERICAL MATHEMATICS, 2023, 186 :289-319

[4] On Relaxed Greedy Randomized Augmented Kaczmarz Methods for Solving Large Sparse Inconsistent Linear Systems [J].

Bai, Zhong-Zhi ;

Wang, Lu ;

Muratova, Galina, V .

EAST ASIAN JOURNAL ON APPLIED MATHEMATICS, 2022, 12 (02) :323-332

[5] ON GREEDY RANDOMIZED AUGMENTED KACZMARZ METHOD FOR SOLVING LARGE SPARSE INCONSISTENT LINEAR SYSTEMS [J].

Bai, Zhong-Zhi ;

Wu, Wen-Ting .

SIAM JOURNAL ON SCIENTIFIC COMPUTING, 2021, 43 (06) :A3892-A3911

[6] On convergence rate of the randomized Gauss-Seidel method [J].

Bai, Zhong-Zhi ;

Wang, Lu ;

Wu, Wen-Ting .

LINEAR ALGEBRA AND ITS APPLICATIONS, 2021, 611 :237-252

[7] On partially randomized extended Kaczmarz method for solving large sparse overdetermined inconsistent linear systems [J].

Bai, Zhong-Zhi ;

Wu, Wen-Ting .

LINEAR ALGEBRA AND ITS APPLICATIONS, 2019, 578 :225-250

[8] On greedy randomized coordinate descent methods for solving large linear least-squares problems [J].

Bai, Zhong-Zhi ;

Wu, Wen-Ting .

NUMERICAL LINEAR ALGEBRA WITH APPLICATIONS, 2019, 26 (04)

[9] On convergence rate of the randomized Kaczmarz method [J].

Bai, Zhong-Zhi ;

Wu, Wen-Ting .

LINEAR ALGEBRA AND ITS APPLICATIONS, 2018, 553 :252-269

[10] On relaxed greedy randomized Kaczmarz methods for solving large sparse linear systems [J].

Bai, Zhong-Zhi ;

Wu, Wen-Ting .

APPLIED MATHEMATICS LETTERS, 2018, 83 :21-26

← 1 2 3 →