×

zbMATH — the first resource for mathematics

Convergence properties of the randomized extended Gauss-Seidel and Kaczmarz methods. (English) Zbl 1327.65112

MSC:
65K05 Numerical mathematical programming methods
15A06 Linear equations (linear algebraic aspects)
90C25 Convex programming
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] C. L. Byrne, Applied Iterative Methods, A K Peters, Wellesley, MA, 2008. · Zbl 1140.65001
[2] Y. Censor, P. P. B. Eggermont, and D. Gordon, Strong underrelaxation in Kaczmarz’s method for inconsistent systems, Numer. Math., 41 (1983), pp. 83–92. · Zbl 0489.65023
[3] X. Chen and A. Powell, Almost sure convergence of the Kaczmarz algorithm with random measurements, J. Fourier Anal. Appl., (2012), pp. 1–20. · Zbl 1268.65042
[5] B. Dumitrescu, On the relation between the randomized extended Kaczmarz algorithm and coordinate descent, BIT, to appear. · Zbl 1332.65056
[6] Y. C. Eldar and D. Needell, Acceleration of randomized Kaczmarz method via the Johnson-Lindenstrauss lemma, Numer. Algorithms, 58 (2011), pp. 163–177. · Zbl 1230.65051
[7] T. Elfving, Block-iterative methods for consistent and inconsistent linear equations, Numer. Math., 35 (1980), pp. 1–12. · Zbl 0416.65031
[8] R. Gordon, R. Bender, and G. T. Herman, Algebraic reconstruction techniques (ART) for three-dimensional electron microscopy and X-ray photography, J. Theoret. Biol., 29 (1970), pp. 471–481.
[9] C. Hamaker and D. C. Solmon, The angles between the null spaces of X-rays, J. Math. Anal. Appl., 62 (1978), pp. 1–23. · Zbl 0437.45025
[10] M. Hanke and W. Niethammer, On the acceleration of Kaczmarz’s method for inconsistent linear systems, Linear Algebra Appl., 130 (1990), pp. 83–98. · Zbl 0708.65033
[11] P. C. Hansen, Regularization tools: A MATLAB package for analysis and solution of discrete ill-posed problems, Numer. Algorithms, 6 (1994), pp. 1–35. · Zbl 0789.65029
[12] G. T. Herman and L. B. Meyer, Algebraic reconstruction techniques can be made computationally efficient, IEEE Trans. Med. Imaging, 12 (1993), pp. 600–609.
[13] G. T. Herman, Fundamentals of Computerized Tomography: Image Reconstruction from Projections, Springer, Dordrecht, The Netherlands, 2009. · Zbl 1280.92002
[14] S. Kaczmarz, Angenäherte auflösung von systemen linearer gleichungen, Bull. Pol. Acad. Sci. Lett. Ser. A, 35 (1937), pp. 335–357.
[15] D. Leventhal and A. S. Lewis, Randomized methods for linear constraints: Convergence rates and conditioning, Math. Oper. Res., 35 (2010), pp. 641–654. · Zbl 1216.15006
[16] J. Liu, S. J. Wright, and S. Sridhar, An Asynchronous Parallel Randomized Kaczmarz Algorithm, preprint, arXiv:1401.4780, 2014.
[17] F. Natterer, The Mathematics of Computerized Tomography, Classics Appl. Math. 32, SIAM, Philadelphia, 2001. · Zbl 0973.92020
[18] D. Needell, Randomized Kaczmarz solver for noisy linear systems, BIT, 50 (2010), pp. 395–403. · Zbl 1195.65038
[19] D. Needell, N. Sbrero, and R. Ward, Stochastic gradient descent and the randomized Kaczmarz algorithm, Math. Program. Series A, to appear. · Zbl 1333.65070
[20] D. Needell and J. A. Tropp, Paved with good intentions: Analysis of a randomized block Kaczmarz method, Linear Algebra Appl., 441 (2014), pp. 199–221. · Zbl 1282.65042
[21] D. Needell and R. Ward, Two-subspace projection method for coherent overdetermined linear systems, J. Fourier Anal. Appl., 19 (2013), pp. 256–269. · Zbl 1306.65190
[22] Yu. Nesterov, Efficiency of coordinate descent methods on huge-scale optimization problems, SIAM J. Optim., 22 (2012), pp. 341–362. · Zbl 1257.90073
[23] C. Popa, Extensions of block-projections methods with relaxation parameters to inconsistent and rank-deficient least-squares problems, BIT, 38 (1998), pp. 151–176. · Zbl 1005.65038
[24] C. Popa, T. Preclik, H. Köstler, and U. Rüde, On Kaczmarz’s projection iteration as a direct solver for linear least squares problems, Linear Algebra Appl., 436 (2012), pp. 389–404. · Zbl 1238.65031
[25] P. Richtárik and M. Takáč, Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function, Math. Program., 144 (2012), pp. 1–38.
[26] T. Strohmer and R. Vershynin, A randomized Kaczmarz algorithm with exponential convergence, J. Fourier Anal. Appl., 15 (2009), pp. 262–278. · Zbl 1169.68052
[27] K. Tanabe, Projection method for solving a singular system of linear equations and its applications, Numer. Math., 17 (1971), pp. 203–214. · Zbl 0228.65032
[28] T. M. Whitney and R. K. Meany, Two algorithms related to the method of steepest descent, SIAM J. Numer. Anal., 4 (1967), pp. 109–118. · Zbl 0173.17806
[29] J. Xu and L. Zikatanov, The method of alternating projections and the method of subspace corrections in Hilbert space, J. Amer. Math. Soc., 15 (2002), pp. 573–597. · Zbl 0999.47015
[30] A. Zouzias and N. M. Freris, Randomized extended Kaczmarz for solving least squares, SIAM J. Matrix Anal. Appl., 34 (2013), pp. 773–793. · Zbl 1273.65053
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.