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 () algorithm is a simple but powerful approach for solving consistent linear systems
. This paper proposes an accelerated randomized Kaczmarz (
) algorithm with better convergence than the standard
algorithm on ill-conditioned problems. The per-iteration cost of
and
are similar if
is dense, but
is much more able to exploit sparsity in
than is
. To deal with the sparse case, an efficient implementation for
, called
, is proposed. A comparison of convergence rates and average per-iteration complexities among
,
, and
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.
- [1] Yair Censor, Dan Gordon, and Rachel Gordon, Component averaging: an efficient iterative parallel algorithm for large and sparse unstructured problems, Parallel Comput. 27 (2001), no. 6, 777-808. MR 1823354 (2002a:65211), https://doi.org/10.1016/S0167-8191(00)00100-9
- [2] Yonina C. Eldar and Deanna Needell, Acceleration of randomized Kaczmarz method via the Johnson-Lindenstrauss lemma, Numer. Algorithms 58 (2011), no. 2, 163-177. MR 2835851 (2012k:65043), https://doi.org/10.1007/s11075-011-9451-z
- [3] A. Galántai, On the rate of convergence of the alternating projection method in finite dimensional spaces, J. Math. Anal. Appl. 310 (2005), no. 1, 30-44. MR 2160671 (2006m:65101), https://doi.org/10.1016/j.jmaa.2004.12.050
- [4] Gabor T. Herman, Image Reconstruction from Projections, The fundamentals of computerized tomography; Computer Science and Applied Mathematics, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1980. MR 630896 (83e:92008)
- [5] G. T. Herman, Fundamentals of Computerized Tomography, Springer, 2009.
- [6] Alan J. Hoffman, On approximate solutions of systems of linear inequalities, J. Research Nat. Bur. Standards 49 (1952), 263-265. MR 0051275 (14,455b)
- [7] S. Kaczmarz, Angenaherte auflsung von systemen linearer gleichungen, Bulletin International de l'Acadmie Polonaise des Sciences et des Letters 35 (1937), 355-357.
- [8] D. Leventhal and A. S. Lewis, Randomized methods for linear constraints: convergence rates and conditioning, Math. Oper. Res. 35 (2010), no. 3, 641-654. MR 2724068 (2012a:65083), https://doi.org/10.1287/moor.1100.0456
- [9] Deanna Needell, Randomized Kaczmarz solver for noisy linear systems, BIT 50 (2010), no. 2, 395-403. MR 2640019 (2011d:65086), https://doi.org/10.1007/s10543-010-0265-5
- [10] Yurii Nesterov, Introductory lectures on convex optimization, A basic course, Applied Optimization, vol. 87, Kluwer Academic Publishers, Boston, MA, 2004. MR 2142598 (2005k:90001)
- [11] Yu. Nesterov, Efficiency of coordinate descent methods on huge-scale optimization problems, SIAM J. Optim. 22 (2012), no. 2, 341-362. MR 2968857, https://doi.org/10.1137/100802001
- [12] Jorge Nocedal and Stephen J. Wright, Numerical Optimization, 2nd ed., Springer Series in Operations Research and Financial Engineering, Springer, New York, 2006. MR 2244940 (2007a:90001)
- [13] Constantin Popa, Characterization of the solutions set of inconsistent least-squares problems by an extended Kaczmarz algorithm, Korean J. Comput. Appl. Math. 6 (1999), no. 1, 51-64. MR 1669567 (2000c:65035)
- [14] Thomas Strohmer and Roman Vershynin, A randomized Kaczmarz algorithm with exponential convergence, J. Fourier Anal. Appl. 15 (2009), no. 2, 262-278. MR 2500924 (2010f:60126), https://doi.org/10.1007/s00041-008-9030-4
- [15] Roman Vershynin, Introduction to the non-asymptotic analysis of random matrices, Compressed sensing, Cambridge Univ. Press, Cambridge, 2012, pp. 210-268. MR 2963170
- [16] A. Zouzias and N. M. Freris, Randomized extended Kaczmarz for solving least-squares, Preprint arXiv:1205.5770v2, 2012.
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