Randomized extended Kaczmarz for solving least squares

Anastasios Zouzias; Nikolaos M. Freris

doi:10.1137/120889897

Randomized extended Kaczmarz for solving least squares

Anastasios Zouzias, Nikolaos M. Freris

Electrical Engineering

Research output: Contribution to journal › Article › peer-review

Abstract

We present a randomized iterative algorithm that exponentially converges in the mean square to the minimum ℓ₂-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.

Original language	English (US)
Pages (from-to)	773-793
Number of pages	21
Journal	SIAM Journal on Matrix Analysis and Applications
Volume	34
Issue number	2
DOIs	https://doi.org/10.1137/120889897
State	Published - 2013

Keywords

Iterative method
LAPACK
Linear least squares
Minimum-length solution
Overdetermined system
Random sampling
Randomized algorithms
Sparse matrix
Underdetermined system

ASJC Scopus subject areas

Analysis

Access to Document

10.1137/120889897

Cite this

@article{a14d27c410fd45a9afb3193d0d6496fa,

title = "Randomized extended Kaczmarz for solving least squares",

abstract = "We present a randomized iterative algorithm that exponentially converges in the mean square to the minimum ℓ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.",

keywords = "Iterative method, LAPACK, Linear least squares, Minimum-length solution, Overdetermined system, Random sampling, Randomized algorithms, Sparse matrix, Underdetermined system",

author = "Anastasios Zouzias and Freris, {Nikolaos M.}",

year = "2013",

doi = "10.1137/120889897",

language = "English (US)",

volume = "34",

pages = "773--793",

journal = "SIAM Journal on Matrix Analysis and Applications",

issn = "0895-4798",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "2",

}

TY - JOUR

T1 - Randomized extended Kaczmarz for solving least squares

AU - Zouzias, Anastasios

AU - Freris, Nikolaos M.

PY - 2013

Y1 - 2013

N2 - We present a randomized iterative algorithm that exponentially converges in the mean square to the minimum ℓ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.

AB - We present a randomized iterative algorithm that exponentially converges in the mean square to the minimum ℓ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.

KW - Iterative method

KW - LAPACK

KW - Linear least squares

KW - Minimum-length solution

KW - Overdetermined system

KW - Random sampling

KW - Randomized algorithms

KW - Sparse matrix

KW - Underdetermined system

UR - http://www.scopus.com/inward/record.url?scp=84880534082&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84880534082&partnerID=8YFLogxK

U2 - 10.1137/120889897

DO - 10.1137/120889897

M3 - Article

AN - SCOPUS:84880534082

SN - 0895-4798

VL - 34

SP - 773

EP - 793

JO - SIAM Journal on Matrix Analysis and Applications

JF - SIAM Journal on Matrix Analysis and Applications

IS - 2

ER -

Randomized extended Kaczmarz for solving least squares

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this