[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 Solver for Linear Systems with Exponential Convergence

  • Conference paper
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX 2006, RANDOM 2006)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 4110))

Abstract

The Kaczmarz method for solving linear systems of equations Ax=b 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 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 its small random part. It thus outperforms all previously known methods on extremely overdetermined systems. Even for moderately overdetermined systems, numerical simulations reveal that our algorithm can converge faster than the celebrated conjugate gradient algorithm.

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

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. 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)

    Google Scholar 

  2. 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 

  3. 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 

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

    Article  MATH  MathSciNet  Google Scholar 

  5. Frieze, A., Kannan, R., Vempala, S.: Fast Monte-Carlo Algorithms for finding low-rank approximations. In: Proceedings of the Foundations of Computer Science, pp. 378–390 (1998); journal version in: Journal of the ACM 51, 1025–1041 (2004)

    Google Scholar 

  6. 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 

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

    Article  MATH  MathSciNet  Google Scholar 

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

    MATH  Google Scholar 

  9. Herman, G.T.: Image reconstruction from projections. In: The fundamentals of computerized tomography. Computer Science and Applied Mathematics. Academic Press Inc. [Harcourt Brace Jovanovich Publishers], New York (1980)

    Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Google Scholar 

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

    MATH  Google Scholar 

  14. Rudelson, M., Vershynin, R.: Sampling from large matrices: an approach through geometric functional analysis (preprint, 2006)

    Google Scholar 

  15. 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. Academic Press, San Diego (1987)

    Google Scholar 

  16. 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 

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

Editor information

Editors and Affiliations

  1. Departament de Llenguatges i Sistemes Informatics, Universitat Politecnica de Catalunya, Campus Nord - Ed. Omega, 240 Jordi Girona Salgado, 1-3 E-08034, Barcelona

    Josep Díaz

  2. Institute for Computer Science, University of Kiel, Olshausenstrasse 40, 24118, Kiel, Germany

    Klaus Jansen

  3. Centre Universitaire d’Informatique, Battelle Bâtiment A, Route de Drize 7,, 1227, Carouge, Geneva, Switzerland

    José D. P. Rolim

  4. School of Computer Science, Tel Aviv University, 69978, Tel Aviv, Israel

    Uri Zwick

Rights and permissions

Reprints and permissions

Copyright information

© 2006 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Strohmer, T., Vershynin, R. (2006). A Randomized Solver for Linear Systems with Exponential Convergence. In: Díaz, J., Jansen, K., Rolim, J.D.P., Zwick, U. (eds) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. APPROX RANDOM 2006 2006. Lecture Notes in Computer Science, vol 4110. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11830924_45

Download citation

  • DOI: https://doi.org/10.1007/11830924_45

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-38044-3

  • Online ISBN: 978-3-540-38045-0

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation