## An accelerated randomized Kaczmarz algorithm

HTML articles powered by AMS MathViewer

- by Ji Liu and Stephen J. Wright PDF
- Math. Comp.
**85**(2016), 153-178 Request permission

## 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

- 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**, DOI 10.1016/S0167-8191(00)00100-9 - 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**, DOI 10.1007/s11075-011-9451-z - 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**, DOI 10.1016/j.jmaa.2004.12.050 - Gabor T. Herman,
*Image reconstruction from projections*, Computer Science and Applied Mathematics, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1980. The fundamentals of computerized tomography. MR**630896** - G. T. Herman,
*Fundamentals of Computerized Tomography*, Springer, 2009. - Alan J. Hoffman,
*On approximate solutions of systems of linear inequalities*, J. Research Nat. Bur. Standards**49**(1952), 263–265. MR**0051275** - S. Kaczmarz,
*Angenaherte auflsung von systemen linearer gleichungen*, Bulletin International de l’Acadmie Polonaise des Sciences et des Letters**35**(1937), 355–357. - 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**, DOI 10.1287/moor.1100.0456 - Deanna Needell,
*Randomized Kaczmarz solver for noisy linear systems*, BIT**50**(2010), no. 2, 395–403. MR**2640019**, DOI 10.1007/s10543-010-0265-5 - Yurii Nesterov,
*Introductory lectures on convex optimization*, Applied Optimization, vol. 87, Kluwer Academic Publishers, Boston, MA, 2004. A basic course. MR**2142598**, DOI 10.1007/978-1-4419-8853-9 - Yu. Nesterov,
*Efficiency of coordinate descent methods on huge-scale optimization problems*, SIAM J. Optim.**22**(2012), no. 2, 341–362. MR**2968857**, DOI 10.1137/100802001 - Jorge Nocedal and Stephen J. Wright,
*Numerical optimization*, 2nd ed., Springer Series in Operations Research and Financial Engineering, Springer, New York, 2006. MR**2244940** - 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** - Thomas Strohmer and Roman Vershynin,
*A randomized Kaczmarz algorithm with exponential convergence*, J. Fourier Anal. Appl.**15**(2009), no. 2, 262–278. MR**2500924**, DOI 10.1007/s00041-008-9030-4 - Roman Vershynin,
*Introduction to the non-asymptotic analysis of random matrices*, Compressed sensing, Cambridge Univ. Press, Cambridge, 2012, pp. 210–268. MR**2963170** - A. Zouzias and N. M. Freris,
*Randomized extended Kaczmarz for solving least-squares*, Preprint arXiv:1205.5770v2, 2012.

## 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
- MR Author ID: 213980
- Email: swright@cs.wisc.edu
- 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. - © Copyright 2015 American Mathematical Society
- Journal: Math. Comp.
**85**(2016), 153-178 - MSC (2010): Primary 65F10; Secondary 68W20
- DOI: https://doi.org/10.1090/mcom/2971
- MathSciNet review: 3404446