[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

A Randomized Kaczmarz Algorithm with Exponential Convergence

  • Published:
Journal of Fourier Analysis and Applications Aims and scope Submit manuscript

Abstract

The Kaczmarz method for solving linear systems of equations is an iterative algorithm that has found many applications ranging from computer tomography to digital signal processing. Despite the popularity of this method, useful theoretical estimates for its rate of convergence are still scarce. We introduce a randomized version of the Kaczmarz method for consistent, overdetermined linear systems and we prove that it converges with expected exponential rate. Furthermore, this is the first solver whose rate does not depend on the number of equations in the system. The solver does not even need to know the whole system but only a small random part of it. It thus outperforms all previously known methods on general extremely overdetermined systems. Even for moderately overdetermined systems, numerical simulations as well as theoretical analysis reveal that our algorithm can converge faster than the celebrated conjugate gradient algorithm. Furthermore, our theory and numerical simulations confirm a prediction of Feichtinger et al. in the context of reconstructing bandlimited functions from nonuniform sampling.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Bass, R.F., Gröchenig, K.: Random sampling of multivariate trigonometric polynomials. SIAM J. Math. Anal. 36(3), 773–795 (2004/05)

    Article  MATH  MathSciNet  Google Scholar 

  2. Benedetto, J.J., Ferreira, P.J.S.G. (eds.): Modern Sampling Theory: Mathematics and Applications. Applied and Numerical Harmonic Analysis. Birkhäuser, Boston (2001)

    Google Scholar 

  3. Cenker, C., Feichtinger, H.G., Mayer, M., Steier, H., Strohmer, T.: New variants of the POCS method using affine subspaces of finite codimension, with applications to irregular sampling. In: Proc. SPIE: Visual Communications and Image Processing, pp. 299–310 (1992)

  4. Censor, Y., Eggermont, P.P.B., Gordon, D.: Strong underrelaxation in Kaczmarz’s method for inconsistent linear systems. Numer. Math. 41, 83–92 (1983)

    Article  MATH  MathSciNet  Google Scholar 

  5. Demmel, J.: The probability that a numerical analysis problem is difficult. Math. Comput. 50(182), 449–480 (1988)

    Article  MATH  MathSciNet  Google Scholar 

  6. Deutsch, F.: Rate of convergence of the method of alternating projections. In: Parametric Optimization and Approximation (Oberwolfach, 1983). Internat. Schriftenreihe Numer. Math., vol. 72, pp. 96–107. Birkhäuser, Basel (1985)

    Google Scholar 

  7. Deutsch, F., Hundal, H.: The rate of convergence for the method of alternating projections. II. J. Math. Anal. Appl. 205(2), 381–405 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  8. Edelman, A.: Eigenvalues and condition numbers of random matrices. SIAM J. Matrix Anal. Appl. 9(4), 543–560 (1988)

    Article  MATH  MathSciNet  Google Scholar 

  9. Edelman, A.: On the distribution of a scaled condition number. Math. Comput. 58(197), 185–190 (1992)

    Article  MATH  MathSciNet  Google Scholar 

  10. Edelman, A., Sutton, B.D.: Tails of condition number distributions. SIAM J. Matrix Anal. Appl. 27(2), 547–560 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  11. Feichtinger, H.G., Gröchenig, K.H.: Theory and practice of irregular sampling. In: Benedetto, J., Frazier, M. (eds.) Wavelets: Mathematics and Applications, pp. 305–363. CRC Press, Boca Raton (1994)

    Google Scholar 

  12. Feichtinger, H.G., Gröchenig, K., Strohmer, T.: Efficient numerical methods in non-uniform sampling theory. Numer. Math. 69, 423–440 (1995)

    Article  MATH  MathSciNet  Google Scholar 

  13. Frieze, A., Kannan, R., Vempala, S.: Fast Monte-Carlo algorithms for finding low-rank approximations. Proc. Found. Comput. Sci. 39, 378–390 (1998). Journal version in J. ACM 51, 1025–1041 (2004)

    Google Scholar 

  14. Galántai, A.: On the rate of convergence of the alternating projection method in finite dimensional spaces. J. Math. Anal. Appl. 310(1), 30–44 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  15. Geman, S.: Limit theorem for the norm of random matrices. Ann. Probab. 8(2), 252–261 (1980)

    Article  MATH  MathSciNet  Google Scholar 

  16. Golub, G.H., van Loan, C.F.: Matrix Computations, 3rd edn. Johns Hopkins, Baltimore (1996)

    MATH  Google Scholar 

  17. Gröchenig, K.: Reconstruction algorithms in irregular sampling. Math. Comput. 59, 181–194 (1992)

    Article  MATH  Google Scholar 

  18. Gröchenig, K.: Irregular sampling, Toeplitz matrices, and the approximation of entire functions of exponential type. Math. Comput. 68, 749–765 (1999)

    Article  MATH  Google Scholar 

  19. Hanke, M.: Conjugate Gradient Type Methods for Ill-Posed Problems. Longman Scientific & Technical, Harlow (1995)

    MATH  Google Scholar 

  20. Hanke, M., Niethammer, W.: On the acceleration of Kaczmarz’s method for inconsistent linear systems. Linear Algebra Appl. 130, 83–98 (1990)

    Article  MATH  MathSciNet  Google Scholar 

  21. Hanke, M., Niethammer, W.: On the use of small relaxation parameters in Kaczmarz’s method. Z. Angew. Math. Mech. 70(6), T575–T576 (1990). Bericht über die Wissenschaftliche Jahrestagung der GAMM (Karlsruhe, 1989)

    MathSciNet  Google Scholar 

  22. Herman, G.T.: Image Reconstruction from Projections. The Fundamentals of Computerized Tomography. Computer Science and Applied Mathematics. Academic Press, New York (1980).

    Google Scholar 

  23. Herman, G.T., Meyer, L.B.: Algebraic reconstruction techniques can be made computationally efficient. IEEE Trans. Medical Imaging 12(3), 600–609 (1993)

    Article  Google Scholar 

  24. Herman, G.T., Lent, A., Lutz, P.H.: Relaxation methods for image reconstruction. Commun. Assoc. Comput. Mach. 21, 152–158 (1978)

    MATH  MathSciNet  Google Scholar 

  25. Hounsfield, G.N.: Computerized transverse axial scanning (tomography): Part I. Description of the system. Br. J. Radiol. 46, 1016–1022 (1973)

    Google Scholar 

  26. Kaczmarz, S.: Angenäherte Auflösung von Systemen linearer Gleichungen. Bull. Int. Acad. Polon. Sci. Lett. A 335–357 (1937)

  27. Natterer, F.: The Mathematics of Computerized Tomography. Wiley, New York (1986)

    MATH  Google Scholar 

  28. Rudelson, M., Vershynin, R.: Sampling from large matrices: an approach through geometric functional analysis. J. ACM 54(4), 21 (2006)

    Article  MathSciNet  Google Scholar 

  29. Rudelson, M., Vershynin, R.: Invertibility of random matrices. I. The smallest singular value is of order n −1/2. Preprint

  30. Rudelson, M., Vershynin, R.: Invertibility of random matrices. II. The Littlewood–Offord theory. Preprint

  31. Sezan, K.M., Stark, H.: Applications of convex projection theory to image recovery in tomography and related areas. In: Stark, H. (ed.) Image Recovery: Theory and Application, pp. 415–462. Acad. Press, San Diego (1987)

    Google Scholar 

  32. Silverstein, J.W.: The smallest eigenvalue of a large-dimensional Wishart matrix. Ann. Probab. 13(4), 1364–1368 (1985)

    Article  MATH  MathSciNet  Google Scholar 

  33. Spielman, D.A., Teng, S.-H.: Smoothed analysis of algorithms. In: Proceedings of the International Congress of Mathematicians, vol. I, pp. 597–606. Higher Ed. Press, Beijing (2002).

    Google Scholar 

  34. Tao, T., Vu, V.: Inverse Littlewood–Offord theorems and the condition number of random discrete matrices. Ann. Math. (2008, to appear)

  35. van der Sluis, A., van der Vorst, H.A.: The rate of convergence of conjugate gradients. Numer. Math. 48, 543–560 (1986)

    Article  MATH  MathSciNet  Google Scholar 

  36. Yeh, S., Stark, H.: Iterative and one-step reconstruction from nonuniform samples by convex projections. J. Opt. Soc. Am. A 7(3), 491–499 (1990)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, University of California, Davis, CA, 95616-8633, USA

    Thomas Strohmer & Roman Vershynin

Authors
  1. Thomas Strohmer
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Roman Vershynin
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Thomas Strohmer.

Additional information

Communicated by Peter G. Casazza.

T. Strohmer was supported by NSF DMS grant 0511461. R. Vershynin was supported by the Alfred P. Sloan Foundation and by NSF DMS grant 0401032.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Strohmer, T., Vershynin, R. A Randomized Kaczmarz Algorithm with Exponential Convergence. J Fourier Anal Appl 15, 262–278 (2009). https://doi.org/10.1007/s00041-008-9030-4

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00041-008-9030-4

Keywords

Search

Navigation