×

zbMATH — the first resource for mathematics

The extensions of convergence rates of Kaczmarz-type methods. (English) Zbl 1452.65062
Summary: Kaczmarz-type methods, such as the randomized Kaczmarz method, the block Kaczmarz method and the Cimmino method, can be derived from the Kaczmarz method. In this paper, we introduce a new error term \(\|x_k-P_{N(A)}x_0-x^\dagger\|_2\) for Kaczmarz-type methods, where \(x^\dagger\) is the generalized solution of \(Ax=b\) and \(P_{N(A)}x_0\) is the orthogonal projection of a given initial value \(x_0\) onto the null space \(N(A)\). It includes the well-known error term \(\|x_k-x_\ast\|_2\) as a special case when \(x_0=0\) and \(x^\dagger=x^\ast\), where \(x^\ast\) is a true solution of \(Ax=b\). We investigate the behavior of the new error term and establish the corresponding convergence rates for Kaczmarz-type methods. Especially, from the estimate of new error term for the Kaczmarz method, we can get a more simple proof for the convergence of the Kaczmarz method.
MSC:
65F10 Iterative numerical methods for linear systems
65F08 Preconditioners for iterative methods
65N22 Numerical solution of discretized equations for boundary value problems involving PDEs
65J20 Numerical solutions of ill-posed problems in abstract spaces; regularization
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Gordon, R.; Bender, R.; Herman, G., Algebraic reconstruction techniques (ART) for three dimensional electron microscopy and x-ray photography, J. Theoret. Biol., 29, 3, 471-481 (1970)
[2] Long, Y.; Fessler, J. A.; Balter, J. M., 3D forward and back-projection for X-ray CT using separable footprints, IEEE Trans. Med. Imaging, 29, 11, 1839-1850 (2010)
[3] Devaney, A. J., A filtered backpropagation algorithm for diffraction tomography, Ultrason. Imaging, 4, 4, 336-350 (1982)
[4] Pan, X.; Dan, X.; Zou, Y.; Yu, L., A unified analysis of FBP-based algorithms in helical cone-beam and circular cone- and fan-beam scans, Phys. Med. Biol., 49, 18, 4349-4369 (2004)
[5] Herman, G. T.; Meyer, L. B., Relaxation method for image reconstruction, Commun. ACM, 21, 2, 152-158 (1978) · Zbl 0367.68065
[6] Natterer, F., The Mathematics of Computerized Tomography (1986), Wiley-Interscience · Zbl 0617.92001
[7] Heffernan, P. B.; Robb, R. A., Image reconstruction from incomplete projection data: iterative reconstruction-projection techniques, IEEE Trans. Biomed. Eng., 30, 12, 838-841 (1983)
[8] Inouye, T., Image reconstruction with limited angle projection data, IEEE Trans. Nucl. Sci., 26, 2, 2665-2669 (1979)
[9] Reeds, J. A.; Shepp, L. A., Limited angle reconstruction in tomography via squashing, IEEE Trans. Med. Imaging, 6, 2, 89-97 (1987)
[10] Candes, E.; Romberg, J.; Tao, T., Stable signal recovery from incomplete and inaccurate measurements, Commun. Pure Appl. Math., 59, 8, 1207-1223 (2006) · Zbl 1098.94009
[11] Tanabe, K., Projection method for solving a singular system of linear equations and its applications, Numer. Math., 17, 3, 203-214 (1971) · Zbl 0228.65032
[12] Herman, G. T.; Meyer, L. B., Algebraic reconstruction techniques can be made computationally efficient, IEEE Trans. Med. Imaging, 12, 3, 600-609 (1993)
[13] Strohmer, T.; Vershynin, R., A randomized kaczmarz algorithm with exponential convergence, J. Fourier Anal. Appl., 15, 2, 262-278 (2009) · Zbl 1169.68052
[14] Demmel, J. W., The probability that a numerical analysis problem is difficult, Math. Comp., 50, 182, 449-480 (1988) · Zbl 0657.65066
[15] Needell, D.; Tropp, J. A., Paved with good intentions: Analysis of a randomized block Kaczmarz method, Linear Algebra Appl., 441, 1, 199-221 (2014) · Zbl 1282.65042
[16] Needell, D.; Zhao, R.; Zouzias, A., Randomized block Kaczmarz method with projection for solving least squares, Linear Algebra Appl., 484, 322-343 (2015) · Zbl 1330.65056
[17] Elfving, T.; Hanson, P. C.; Nikazad, T., Semi-convergence properties of Kaczmarz’s method, Inverse Problems, 30, 5 (2014) · Zbl 1296.65054
[18] Hanke, M., Regularizing properties of a truncated Newton-CG algorithm for nonlinear inverse problems, Numer. Funct. Anal. Optim., 18, 9, 971-993 (1997) · Zbl 0899.65038
[19] Engl, H. W.; Kunisch, K.; Neubauer, A., Convergence rates for Tikhonov regularisation of non-linear ill-posed problems, Inverse Problems, 5, 4, 523-540 (1989) · Zbl 0695.65037
[20] Engl, H. W.; Hanke, M.; Neubauer, A., Regularization of Inverse Problems (1996), Kluwer Academic · Zbl 0859.65054
[21] Jiao, Y.; Jin, B.; Lu, X., Preasymptotic convergence of randomized Kaczmarz method, Inverse Problems, 33, 12 (2017) · Zbl 1382.65087
[22] Needell, D., Randomized Kaczmarz solver for noisy linear systems, BIT Numer. Math., 50, 2, 395-403 (2010) · Zbl 1195.65038
[23] Zouzias, A.; Freris, N. M., Randomized extended Kaczmarz solver for solving least squares, SIAM J. Matrix Anal. Appl., 34, 2, 773-793 (2013) · Zbl 1273.65053
[24] Ma, A.; Needell, D.; Ramdas, A., Convergence properties of the randomized extended Gauss-Seidel and Kaczmarz methods, SIAM J. Matrix Anal. Appl., 36, 4, 1590-1604 (2015) · Zbl 1327.65112
[25] Kang, C.-G.; Zhou, H., The property of analysis of the convergent solution to kaczmarz method, CT Theory Appl., 24, 5, 701-709 (2015)
[26] Popa, C., Least-squares solution of overdetermined inconsistent linear systems using Kaczmarz’s relaxation, Int. J. Comput. Math., 55, 1-2, 79-89 (1995) · Zbl 0830.65027
[27] Boyd, S.; Parikh, N.; Chu, E.; Peleato, B.; Eckstein, J., Distributed optimization and statistical learning via the alternating direction method of multipliers, Found. Trends Mach. Learn., 3, 1, 1-122 (2010) · Zbl 1229.90122
[28] Hansen, P. C., Regularization tools: A matlab package for analysis and solution of discrete ill-posed problems, Numer. Algorithms, 6, 1, 1-35 (1994) · Zbl 0789.65029
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.