RANDOMIZED EXTENDED KACZMARZ FOR SOLVING LEAST SQUARES

被引：240

作者：

Zouzias, Anastasios ^{[1
]}

Freris, Nikolaos M. ^{[2
]}

机构：

[1] Univ Toronto, Dept Comp Sci, Toronto, ON, Canada

[2] Ecole Polytech Fed Lausanne, Sch Comp & Commun Sci IC, CH-1015 Lausanne, Switzerland

来源：

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS | 2013年 / 34卷 / 02期

关键词：

linear least squares; minimum-length solution; sparse matrix; overdetermined system; underdetermined system; iterative method; random sampling; LAPACK; randomized algorithms; ALGEBRAIC RECONSTRUCTION TECHNIQUES; LINEAR-EQUATIONS; ALGORITHM; SYSTEMS; APPROXIMATION;

D O I：

10.1137/120889897

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We present a randomized iterative algorithm that exponentially converges in the mean square to the minimum l(2)-norm least squares solution of a given linear system of equations. The expected number of arithmetic operations required to obtain an estimate of given accuracy is proportional to the squared condition number of the system multiplied by the number of nonzero entries of the input matrix. The proposed algorithm is an extension of the randomized Kaczmarz method that was analyzed by Strohmer and Vershynin.

引用

页码：773 / 793

页数：21

共 51 条

[1]

Angerson E., 1990, Proceedings of Supercomputing '90 (Cat. No.90CH2916-5), P2, DOI 10.1109/SUPERC.1990.129995

[2]

[Anonymous], 2002, TECHNICAL REPORT

[3]

[Anonymous], COMP SCI APPL MATH

[4]

[Anonymous], 1989, TECHNICAL REPORT

[5]

[Anonymous], PREPRINT

[6]

[Anonymous], ROUNDING ERROR UNPUB

[7]

[Anonymous], IEEE C DEC CONTR CDC

[8]

[Anonymous], 1992, VISUAL COMMUN-US, DOI DOI 10.1117/12.131447

[9]

[Anonymous], 1993, ERROR ANAL STATIONAR

[10]

[Anonymous], 2004, ADV MATH

← 1 2 3 4 5 6 →