  We present a randomized iterative algorithm that exponentially converges in
expectation to the minimum Euclidean 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 square
condition number of the system multiplied by the number of non-zeros entries of
the input matrix. The proposed algorithm is an extension of the randomized
Kaczmarz method that was analyzed by Strohmer and Vershynin.
