Randomized Extended Kaczmarz For Solving Least Squares

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.


Published in:
Siam Journal On Matrix Analysis And Applications, 34, 2, 773-793
Year:
2013
Publisher:
Philadelphia, Society for Industrial and Applied Mathematics
ISSN:
0895-4798
Keywords:
Laboratories:




 Record created 2013-10-01, last modified 2018-03-17


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)