Randomized Block Kaczmarz Method with Projection for Solving Least Squares

Authors

Deanna Needell, Claremont McKenna CollegeFollow
Ran Zhao
Anastasios Zouzias

Document Type

Article - preprint

Department

Mathematics (CMC)

Publication Date

3-17-2014

Abstract

The Kaczmarz method is an iterative method for solving overcomplete linear systems of equations Ax = b. The randomized version of the Kaczmarz method put forth by Strohmer and Vershynin iteratively projects onto a randomly chosen solution space given by a single row of the matrix A and converges exponentially in expectation to the solution of a consistent system. In this paper we analyze two block versions of the method each with a randomized projection, that converge in expectation to the least squares solution of inconsistent systems. Our approach utilizes a paving of the matrix A to guarantee exponential convergence, and suggests that paving yields a significant improvement in performance in certain regimes. The proposed method is an extension of the block Kaczmarz method analyzed by Needell and Tropp and the Randomized Extended Kaczmarz method of Zouzias and Freris. The contribution is thus two-fold; unlike the standard Kaczmarz method, our methods converge to the leas-squares solution of inconsistent systems, and by using appropriate blocks of the matrix this convergence can be significantly accelerated. Numerical experiments suggest that the proposed algorithm can indeed lead to advantages in practice.

Comments

Featured in Linear Algebra and its Applications, vol. 484, 322–343, 2015.

Rights Information

© 2014 Needell, Zhao, Zouzias

Terms of Use & License Information

Terms of Use for work posted in Scholarship@Claremont.

Recommended Citation

Needell, D., Zhao, R., Zouzias, A., "Randomized Block Kaczmarz Method with Projection for Solving Least Squares", Submitted, arXiv preprint arXiv:1403.4192, 2014.