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

Randomized Kaczmarz solver for noisy linear systems

  • Published:
BIT Numerical Mathematics Aims and scope Submit manuscript

Abstract

The Kaczmarz method is an iterative algorithm for solving systems of linear equations Ax=b. Theoretical convergence rates for this algorithm were largely unknown until recently when work was done on a randomized version of the algorithm. It was proved that for overdetermined systems, the randomized Kaczmarz method converges with expected exponential rate, independent of the number of equations in the system. Here we analyze the case where the system Ax=b is corrupted by noise, so we consider the system Ax≈b+r where r is an arbitrary error vector. We prove that in this noisy version, the randomized method reaches an error threshold dependent on the matrix A with the same rate as in the error-free case. We provide examples showing our results are sharp in the general context.

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

  2. Censor, Y., Herman, G.T., Jiang, M.: A note on the behavior of the randomized Kaczmarz algorithm of Strohmer and Vershynin. J. Fourier Anal. Appl. 15, 431–436 (2009)

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

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

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

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

    Article  Google Scholar 

  7. Horn, R.A., Johnson, C.R.: Matrix Analysis. Cambridge Univ. Press, Cambridge (1985)

    MATH  Google Scholar 

  8. Kaczmarz, S.: Approximate solution of systems of linear equations. Bull. Acad. Pol. Sci., Lett. A 35, 335–357 (1937) (in German); English transl.: Int. J. Control 57(6), 1269–1271 (1993)

    Google Scholar 

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

    MATH  Google Scholar 

  10. Shapiro, A.: Upper bounds for nearly optimal diagonal scaling of matrices. Linear Multilinear Algebra 29, 145–147 (1991)

    Article  MATH  Google Scholar 

  11. 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, vol. 4110, pp. 499–507. Springer, Berlin (2006)

    Google Scholar 

  12. Strohmer, T., Vershynin, R.: Comments on the randomized Kaczmarz method. J. Fourier Anal. Appl. 15, 437–440 (2009)

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  14. van der Sluis, A.: Condition numbers and equilibration of matrices. Numer. Math. 14, 14–23 (1969)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Statistics, Stanford University, Stanford, CA, 94305-4065, USA

    Deanna Needell

Authors
  1. Deanna Needell
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Deanna Needell.

Additional information

Communicated by Lars Eldén.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Needell, D. Randomized Kaczmarz solver for noisy linear systems. Bit Numer Math 50, 395–403 (2010). https://doi.org/10.1007/s10543-010-0265-5

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10543-010-0265-5

Keywords

Mathematics Subject Classification (2000)

Search

Navigation