×

Nonlinear Kaczmarz algorithms and their convergence. (English) Zbl 1473.65060

Summary: This paper proposes a class of randomized Kaczmarz algorithms for obtaining isolated solutions of large-scale well-posed or overdetermined nonlinear systems of equations. This type of algorithm improves the classic Newton method. Each iteration only needs to calculate one row of the Jacobian instead of the entire matrix, which greatly reduces the amount of calculation and storage. Therefore, these algorithms are called matrix-free algorithms. According to the different probability selection patterns of choosing a row of the Jacobian matrix, the nonlinear Kaczmarz (NK) algorithm, the nonlinear randomized Kaczmarz (NRK) algorithm and the nonlinear uniformly randomized Kaczmarz (NURK) algorithm are proposed. In addition, the NURK algorithm is similar to the stochastic gradient descent (SGD) algorithm in nonlinear optimization problems. The only difference is the choice of step size. In the case of noise-free data, theoretical analysis and the results of numerical based on the classical tangential cone conditions show that the algorithms proposed in this paper are superior to the SGD algorithm in terms of iterations and calculation time.

MSC:

65H10 Numerical computation of solutions to systems of equations
65J20 Numerical solutions of ill-posed problems in abstract spaces; regularization

Software:

minpack
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Byrd, R. H.; Nocedal, J.; Schnabel, R. B., Representations of quasi-Newton matrices and their use in limited memory methods, Math. Program., 63, 1-3, 129-156 (1994) · Zbl 0809.90116
[2] Heinz, W.; Engl, J., Variational methods in imaging, Siam Rev. (2010)
[3] T. Schuster, B. Kaltenbacher, B. Hofmann, K.S. Kazimierski, Regularization Methods in Banach Spaces, De Gruyter, 0000. · Zbl 1259.65087
[4] Kaczmarz, S., Angenaherte auflosung von systemen linearer gleichungenti bulletin international de lacademie polonaise des sciences et des lettres, Classe Sci. Math. Natl. Ser. A Sci. Math., 355-357 (2020)
[5] C. Popa, Projection algorithms-classical results and developments, https://www.lap-publishing.com/, 0000.
[6] Scherzer, O.; Leitao, A.; Kowar, R.; Haltmeier, M., Kaczmarz methods for regularizing nonlinear ill-posed equa- tions ii: Applications, Inverse Probl. Imaging, 1, 3, 507-523 (2017) · Zbl 1135.65026
[7] Strohmer, T.; Vershynin, R., A randomized kaczmarz algorithm with exponential convergence, J. Fourier Anal. Appl., 15, 2, 262 (2009) · Zbl 1169.68052
[8] Kannan, R., Relaxation Methods in Nonlinear Problems (1984), Springer Berlin Heidelberg · Zbl 0568.65036
[9] Brewster, M. E.; Kannan, R., Nonlinear successive over-relaxation, Numer. Math., 44, 2, 309-315 (1984) · Zbl 0566.65045
[10] Brewster, M. E.; Kannan, R., Global convergence of nonlinear successive overrelaxation via linear theory, Computing, 34, 1, 73-79 (1985) · Zbl 0568.65034
[11] Brewster, M. E.; Kannan, R., Varying relaxation parameters in nonlinear successive overrelaxation, Computing, 34, 1, 81-85 (1985) · Zbl 0568.65035
[12] Brewster, M. E.; Kannan, R., A computational process for choosing the relaxation parameter in nonlinear SOR, Computing, 37, 1, 19-29 (1986) · Zbl 0584.65038
[13] Ecker, A.; Gross, D., A system of simultaneous non-linear equations in three-thousand variables, J. Comput. Phys., 64, 1, 246-252 (1986) · Zbl 0627.65055
[14] Vrahatis, M. N.; Bountis, T.; Budinsky, N., A convergence-improving iterative method for computing periodic orbits near bifurcation points, J. Comput. Phys., 88, 1, 1-14 (1990) · Zbl 0704.65056
[15] Scherzer, O.; Leitao, A.; Haltmeier, M., Kaczmarz methods for regularizing nonlinear ill-posed equations i: con- vergence analysis, Inverse Probl. Imaging, 1, 2, 289-298 (2007) · Zbl 1123.65051
[16] Hanke, M.; Neubauer, A.; Scherzer, O., A convergence analysis of the landweber iteration for nonlinear ill-posed problems, Numer. Math., 72, 1, 21-37 (1995) · Zbl 0840.65049
[17] Jin, B.; Zhou, Z.; Zou, J., On the convergence of stochastic gradient descent for nonlinear ill-posed problems (2019)
[18] Deanna Needell, . Srebro, . Nathan, . Ward, . Rachel, Stochastic gradient descent, weighted sampling, and the ran- domized kaczmarz algorithm, Math. Program. · Zbl 1333.65070
[19] Needell, D., Randomized kaczmarz solver for noisy linear systems, BIT Numer. Math., 50, 2, 395-403 (2010) · Zbl 1195.65038
[20] Robbins, H.; Monro, S., A stochastic approximation method, Ann. Math. Stats, 22, 3, 400-407 (1951) · Zbl 0054.05901
[21] Landweber, L., An iteration formula for fredholm integral equations of the first kind, Amer. J. Math., 73, 3, 615-624 (1951) · Zbl 0043.10602
[22] Kelley, C. T., Iterative methods for linear and nonlinear equations, Front. Appl. Math., 16, 4, 206-207 (1995) · Zbl 0832.65046
[23] Madsen, K.; Nielsen, H.; Tingleff, O., Methods for non-linear least square problems (2004)
[24] Hottel, H. C.; Sarofim, A. F., Radiative transfer landolt-Bornstein - group VI, Astron. Astrophys., 142, 9, 42-44 (1967)
[25] More, J. J.; Garbow, B. S.; Hillstrom, K. E., Testing unconstrained optimization software, Acm Trans. Math. Softw., 7, 1, 17-41 (1981) · Zbl 0454.65049
[26] Gomes-Ruggiero, M. A.; Martänez, J. M.; Moretti, A. C., Comparing algorithms for solving sparse nonlinear systems of equations, Siam J. Sci. Statist. Comput., 13, 2, 459-483 (1992) · Zbl 0752.65039
[27] Lukšan, Ladislav, Inexact trust region method for large sparse nonlinear least squares, Kybern. Praha, 29, 4, 305-324 (1993) · Zbl 0806.65060
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.