A randomized Kaczmarz algorithm with exponential convergence. (English) Zbl 1169.68052
The authors introduce a randomized version of the Kaczmarz method (it is an algorithm for solving linear systems) and prove that it converges with expected exponential rate. The rate does not depend on the number of equations in the system and the solver needs to know only a small random part of the system and not the whole system. They discuss conditions under which their algorithm is optimal in a certain sense, as well as the optimality of the estimate on the expected rate of convergence. They also give numerical experiments and compare the convergence of their algorithm with other algorithms.
Reviewer: Chrysoula G. Kokologiannaki (Patras)
References:
| [1] | Bass, R.F., Gröchenig, K.: Random sampling of multivariate trigonometric polynomials. SIAM J. Math. Anal. 36(3), 773–795 (2004/05) · Zbl 1096.94008 · doi:10.1137/S0036141003432316 |
| [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) |
| [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) · Zbl 0489.65023 · doi:10.1007/BF01396307 |
| [5] | Demmel, J.: The probability that a numerical analysis problem is difficult. Math. Comput. 50(182), 449–480 (1988) · Zbl 0657.65066 · doi:10.1090/S0025-5718-1988-0929546-7 |
| [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) |
| [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) · Zbl 0890.65053 · doi:10.1006/jmaa.1997.5202 |
| [8] | Edelman, A.: Eigenvalues and condition numbers of random matrices. SIAM J. Matrix Anal. Appl. 9(4), 543–560 (1988) · Zbl 0678.15019 · doi:10.1137/0609045 |
| [9] | Edelman, A.: On the distribution of a scaled condition number. Math. Comput. 58(197), 185–190 (1992) · Zbl 0745.15012 · doi:10.1090/S0025-5718-1992-1106966-2 |
| [10] | Edelman, A., Sutton, B.D.: Tails of condition number distributions. SIAM J. Matrix Anal. Appl. 27(2), 547–560 (2005) · Zbl 1093.15010 · doi:10.1137/040614256 |
| [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) · Zbl 1090.94524 |
| [12] | Feichtinger, H.G., Gröchenig, K., Strohmer, T.: Efficient numerical methods in non-uniform sampling theory. Numer. Math. 69, 423–440 (1995) · Zbl 0837.65148 · doi:10.1007/s002110050101 |
| [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) · Zbl 1125.65005 |
| [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) · Zbl 1074.65059 · doi:10.1016/j.jmaa.2004.12.050 |
| [15] | Geman, S.: Limit theorem for the norm of random matrices. Ann. Probab. 8(2), 252–261 (1980) · Zbl 0428.60039 · doi:10.1214/aop/1176994775 |
| [16] | Golub, G.H., van Loan, C.F.: Matrix Computations, 3rd edn. Johns Hopkins, Baltimore (1996) · Zbl 0865.65009 |
| [17] | Gröchenig, K.: Reconstruction algorithms in irregular sampling. Math. Comput. 59, 181–194 (1992) · Zbl 0756.65159 |
| [18] | Gröchenig, K.: Irregular sampling, Toeplitz matrices, and the approximation of entire functions of exponential type. Math. Comput. 68, 749–765 (1999) · Zbl 1043.42001 · doi:10.1090/S0025-5718-99-01029-7 |
| [19] | Hanke, M.: Conjugate Gradient Type Methods for Ill-Posed Problems. Longman Scientific & Technical, Harlow (1995) · Zbl 0830.65043 |
| [20] | 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 |
| [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) · Zbl 0716.65040 |
| [22] | Herman, G.T.: Image Reconstruction from Projections. The Fundamentals of Computerized Tomography. Computer Science and Applied Mathematics. Academic Press, New York (1980). · Zbl 0538.92005 |
| [23] | Herman, G.T., Meyer, L.B.: Algebraic reconstruction techniques can be made computationally efficient. IEEE Trans. Medical Imaging 12(3), 600–609 (1993) · doi:10.1109/42.241889 |
| [24] | Herman, G.T., Lent, A., Lutz, P.H.: Relaxation methods for image reconstruction. Commun. Assoc. Comput. Mach. 21, 152–158 (1978) · Zbl 0367.68065 |
| [25] | Hounsfield, G.N.: Computerized transverse axial scanning (tomography): Part I. Description of the system. Br. J. Radiol. 46, 1016–1022 (1973) · doi:10.1259/0007-1285-46-552-1016 |
| [26] | Kaczmarz, S.: Angenäherte Auflösung von Systemen linearer Gleichungen. Bull. Int. Acad. Polon. Sci. Lett. A 335–357 (1937) · Zbl 0017.31703 |
| [27] | Natterer, F.: The Mathematics of Computerized Tomography. Wiley, New York (1986) · Zbl 0617.92001 |
| [28] | Rudelson, M., Vershynin, R.: Sampling from large matrices: an approach through geometric functional analysis. J. ACM 54(4), 21 (2006) · Zbl 1326.68333 · doi:10.1145/1255443.1255449 |
| [29] | Rudelson, M., Vershynin, R.: Invertibility of random matrices. I. The smallest singular value is of order n /2. Preprint · Zbl 1183.15031 |
| [30] | Rudelson, M., Vershynin, R.: Invertibility of random matrices. II. The Littlewood–Offord theory. Preprint · Zbl 1139.15015 |
| [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) |
| [32] | Silverstein, J.W.: The smallest eigenvalue of a large-dimensional Wishart matrix. Ann. Probab. 13(4), 1364–1368 (1985) · Zbl 0591.60025 · doi:10.1214/aop/1176992819 |
| [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). · Zbl 1056.65148 |
| [34] | Tao, T., Vu, V.: Inverse Littlewood–Offord theorems and the condition number of random discrete matrices. Ann. Math. (2008, to appear) · Zbl 1250.60023 |
| [35] | van der Sluis, A., van der Vorst, H.A.: The rate of convergence of conjugate gradients. Numer. Math. 48, 543–560 (1986) · Zbl 0596.65015 · doi:10.1007/BF01389450 |
| [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) · doi:10.1364/JOSAA.7.000491 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
