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?)

  • [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.

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

American Mathematical Society