×

zbMATH — the first resource for mathematics

Randomized Kaczmarz solver for noisy linear systems. (English) Zbl 1195.65038
The method of S. Kaczmarz [Bull. Int. Acad. Polon. Sci. A 1937, 355–357 (1937; Zbl 0017.31703)] is an iterative algorithm for solving systems of linear equations \(A x = b\). It is proved that in the noisy version \(A x \approx b+r,\) where \(r\) is an arbitrary error vector, the randomized method reaches an error threshold dependent on the matrix \(A\) with the same rate as in the error-free case. Examples are shown that the authors results are sharp in the general context.

MSC:
65F10 Iterative numerical methods for linear systems
60H25 Random operators and equations (aspects of stochastic analysis)
65C50 Other computational problems in probability (MSC2010)
PDF BibTeX XML Cite
Full Text: DOI arXiv
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) · Zbl 1177.68252 · doi:10.1007/s00041-009-9077-x
[3] Deutsch, F., Hundal, H.: The rate of convergence for the method of alternating projections. J. Math. Anal. Appl. 205(2), 381–405 (1997) · Zbl 0890.65053 · doi:10.1006/jmaa.1997.5202
[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) · Zbl 1074.65059 · doi:10.1016/j.jmaa.2004.12.050
[5] Hanke, M., Niethammer, W.: On the acceleration of Kaczmarz’s method for inconsistent linear systems. Linear Algebra Appl. 130, 83–98 (1990) · Zbl 0708.65033 · doi:10.1016/0024-3795(90)90207-S
[6] Herman, G.T., Meyer, L.B.: Algebraic reconstruction techniques can be made computationally efficient. IEEE Trans. Med. Imaging 12(3), 600–609 (1993) · doi:10.1109/42.241889
[7] Horn, R.A., Johnson, C.R.: Matrix Analysis. Cambridge Univ. Press, Cambridge (1985) · Zbl 0576.15001
[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)
[9] Natterer, F.: The Mathematics of Computerized Tomography. Wiley, New York (1986) · Zbl 0617.92001
[10] Shapiro, A.: Upper bounds for nearly optimal diagonal scaling of matrices. Linear Multilinear Algebra 29, 145–147 (1991) · Zbl 0726.15003 · doi:10.1080/03081089108818065
[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) · Zbl 1155.65323
[12] Strohmer, T., Vershynin, R.: Comments on the randomized Kaczmarz method. J. Fourier Anal. Appl. 15, 437–440 (2009) · Zbl 1177.68253 · doi:10.1007/s00041-009-9082-0
[13] Strohmer, T., Vershynin, R.: A randomized Kaczmarz algorithm with exponential convergence. J. Fourier Anal. Appl. 15, 262–278 (2009) · Zbl 1169.68052 · doi:10.1007/s00041-008-9030-4
[14] van der Sluis, A.: Condition numbers and equilibration of matrices. Numer. Math. 14, 14–23 (1969) · Zbl 0182.48906 · doi:10.1007/BF02165096
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.