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

Acceleration of randomized Kaczmarz method via the Johnson–Lindenstrauss Lemma

  • Original Paper
  • Published:
Numerical Algorithms Aims and scope Submit manuscript

Abstract

The Kaczmarz method is an algorithm for finding the solution to an overdetermined consistent system of linear equations Ax = b by iteratively projecting onto the solution spaces. The randomized version put forth by Strohmer and Vershynin yields provably exponential convergence in expectation, which for highly overdetermined systems even outperforms the conjugate gradient method. In this article we present a modified version of the randomized Kaczmarz method which at each iteration selects the optimal projection from a randomly chosen set, which in most cases significantly improves the convergence rate. We utilize a Johnson–Lindenstrauss dimension reduction technique to keep the runtime on the same order as the original randomized version, adding only extra preprocessing time. We present a series of empirical studies which demonstrate the remarkable acceleration in convergence to the solution using this modified approach.

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. Achlioptas, D.: Database-friendly random projections: Johnson–Lindenstrauss with binary coins. J. Comput. Syst. Sci. 66(4), 671–687 (2003) (Special issue of invited papers from PODS’01)

    Article  MathSciNet  MATH  Google Scholar 

  2. Ailon, N., Chazelle, B.: The fast johnson-lindenstrauss transform and approximate nearest neighbors. SIAM J. Comput. 39, 302–322 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  3. Ailon, N., Liberty, E.: Almost optimal unrestricted fast johnson-lindenstrauss transform. Available at http://arxiv.org/abs/1005.5513 (2010)

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

  5. Chan, T.F., Wan, W.L.: Analysis of projection methods for solving linear systems with multiple right-hand sides. SIAM J. Sci. Comput. 18, 1698–1721 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  6. Dasgupta, D., Gupta, A.: An elementary proof of the Johnson–Lindenstrauss lemma. Tech. Report 99-006, U.C. Berkeley (1999)

  7. Dasgupta, S., Gupta, A.: An elementary proof of a theorem of Johnson and Lindenstrauss. Random Struct. Algorithms 22(1), 60–65 (2003)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  9. Drineas, P., Mahoney, M.W., Muthukrishnan, S.: Sampling algorithms for ℓ2 regression and applications. In: Proc. 17th Ann. ACM-SIAM Symp. on Discrete Algorithms, pp. 1127–1136 (2006)

  10. Drineas, P., Mahoney, M.W., Muthukrishnan, S.: Relative-error CUR matrix decompositions. SIAM J. Matrix Anal. A 30, 844–881 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  11. Farhat, C., Roux, F.X.: Implicit parallel processing in structural mechanics. Tech. report cu-cssc-93-26, Center for Aerospace Structures, University of Colorado, Boulder, CO (1993)

  12. 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  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  Google Scholar 

  15. Hinrichs, A., Vybiral, J.: Johnson-lindenstrauss lemma for circulant matrices. Random Struct. Algor. (to appear)

  16. Indyk, P., Motwani, R.: Approximate nearest neighbors: towards removing the curse of dimensionality. In: Symp. on Theory of Computing, pp. 604–613 (1998)

  17. Johnson, W.B., Lindenstrauss, J.: Extensions of Lipschitz mappings into a Hilbert space. In: Conf. in Modern Analysis and Probability, pp. 189–206 (1984)

  18. Kaczmarz, S.: Angenäherte Auflösung von Systemen linearer Gleichungen. Bulletin International de l’Académie Polonaise des Sciences et des Lettres. Classe des Sciences Mathématiques et Naturelles. Série A, Sciences Mathématiques 35, 335–357 (1937)

    Google Scholar 

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

    MATH  Google Scholar 

  20. Needell, D.: Randomized Kaczmarz solver for noisy linear systems. BIT Num. Math. 50(2), 395–403 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  21. 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, New York (1987)

    Google Scholar 

  22. Smith, C.F., Peterson, A.F., Mittra, R.: A conjugate gradient algorithm for the treatment of multiple incident electromagnetic fields. IEEE Trans. Antennas Propag. 37, 1490–1493 (1989)

    Article  Google Scholar 

  23. Strohmer, T.: A levinson-galerkin algorithm for regularized trigonometric approximation. SIAM J. Sci. Comput. 22(4), 1160–1183 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  24. Strohmer, T., Vershynin, R.: A randomized solver for linear systems with exponential convergence. In: RANDOM 2006 (10th International Workshop on Randomization and Computation). Lecture Notes in Computer Science, number 4110, pp. 499–507. Springer (2006)

  25. Strohmer, T., Vershynin, R.: A randomized Kaczmarz algorithm with exponential convergence. J. Fourier Anal. Appl. 15, 262–278 (2009)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Electrical Engineering, Technion - Israel Institute of Technology, Haifa, 32000, Israel

    Yonina C. Eldar

  2. Department of Statistics, Stanford University, Stanford, CA, 94305, USA

    Deanna Needell

Authors
  1. Yonina C. Eldar
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Deanna Needell
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Deanna Needell.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Eldar, Y.C., Needell, D. Acceleration of randomized Kaczmarz method via the Johnson–Lindenstrauss Lemma. Numer Algor 58, 163–177 (2011). https://doi.org/10.1007/s11075-011-9451-z

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11075-011-9451-z

Keywords

Search

Navigation