Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

Request Permissions   Purchase Content 
 

 

An accelerated randomized Kaczmarz algorithm


Authors: Ji Liu and Stephen J. Wright
Journal: Math. Comp. 85 (2016), 153-178
MSC (2010): Primary 65F10; Secondary 68W20
DOI: https://doi.org/10.1090/mcom/2971
Published electronically: May 29, 2015
MathSciNet review: 3404446
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The randomized Kaczmarz ($ \rm {RK}$) algorithm is a simple but powerful approach for solving consistent linear systems $ Ax=b$. This paper proposes an accelerated randomized Kaczmarz ($ \rm {ARK}$) algorithm with better convergence than the standard $ \rm {RK}$ algorithm on ill-conditioned problems. The per-iteration cost of $ \rm {RK}$ and $ \rm {ARK}$ are similar if $ A$ is dense, but $ \rm {RK}$ is much more able to exploit sparsity in $ A$ than is $ \rm {ARK}$. To deal with the sparse case, an efficient implementation for $ \rm {ARK}$, called $ \rm {SARK}$, is proposed. A comparison of convergence rates and average per-iteration complexities among $ \rm {RK}$, $ \rm {ARK}$, and $ \rm {SARK}$ is given, taking into account different levels of sparseness and conditioning. Comparisons with the leading deterministic algorithm -- conjugate gradient applied to the normal equations -- are also given. Finally, the analysis is validated via computational testing.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 65F10, 68W20

Retrieve articles in all journals with MSC (2010): 65F10, 68W20


Additional Information

Ji Liu
Affiliation: Department of Computer Sciences, University of Wisconsin-Madison, Madison, Wisconsin 53706-1685
Address at time of publication: Department of Computer Sciences, 1210 W. Dayton St., Madison, Wisconsin 53706-1685
Email: ji.liu.uwisc@gmail.com

Stephen J. Wright
Affiliation: Department of Computer Sciences, University of Wisconsin-Madison, Madison, Wisconsin 53706-1685
Email: swright@cs.wisc.edu

DOI: https://doi.org/10.1090/mcom/2971
Keywords: Linear equations, randomized methods, Nesterov acceleration
Received by editor(s): October 8, 2013
Received by editor(s) in revised form: May 25, 2014
Published electronically: May 29, 2015
Additional Notes: The first author was supported in part by NSF Awards DMS-0914524 and DMS-1216318 and ONR Award N00014-13-1-0129.
The second author was supported in part by NSF Awards DMS-0914524 and DMS-1216318, ONR Award N00014-13-1-0129, DOE Award DE-SC0002283, and Subcontract 3F-30222 from Argonne National Laboratory.
Article copyright: © Copyright 2015 American Mathematical Society