Randomized extended Kaczmarz for solving least squares

Anastasios Zouzias, Nikolaos M. Freris

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)773-793
Number of pages21
JournalSIAM Journal on Matrix Analysis and Applications
Issue number2
StatePublished - 2013


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

ASJC Scopus subject areas

  • Analysis


Dive into the research topics of 'Randomized extended Kaczmarz for solving least squares'. Together they form a unique fingerprint.

Cite this