On a Nonlinear Fast Deterministic Block Kaczmarz Method for Solving Nonlinear Equations

Abstract

For solving large-scale nonlinear equations, a nonlinear fast deterministic block Kaczmarz method based on a greedy strategy is proposed. The method is adaptive and does not need to compute the pseudoinverses of submatrices. It is proved that the method will converge linearly to the nearest solution to the initial point under mild conditions. Numerical experiments are performed to illustrate that the method is efficient at least for the tested problems.

Keywords

Greedy / Deterministic / Block / Kaczmarz / Newton / Convergence

References

[1] AlamSMS, NatarajanB, PahwaA. Distribution grid state estimation from compressed measurements. IEEE Trans. Smart Grid, 2014, 5: 1631-1642

[2] AnH-B, BaiZ-Z. NGLM: a globally convergent Newton-GMRES method (in Chinese). Math. Numer. Sin., 2005, 27: 151-174

[3] AnH-B, BaiZ-Z. A globally convergent Newton-GMRES method for large sparse systems of nonlinear equations. Appl. Numer. Math., 2007, 57: 235-252

[4] BaiZ-Z, AnH-B. On efficient variants and global convergence of the Newton-GMRES method (in Chinese). J. Numer. Methods Comput. Appl., 2005, 26: 291-300

[5] BaiZ-Z, GuoX-P. On Newton-HSS methods for systems of nonlinear equations with positive-definite Jacobian matrices. J. Comput. Math., 2010, 28: 235-260

[6] BaiZ-Z, WangL. On convergence rates of Kaczmarz-type methods with different selection rules of working rows. Appl. Numer. Math., 2023, 186: 289-319

[7] BaiZ-Z, WuW-T. On greedy randomized Kaczmarz method for solving large sparse linear systems. SIAM J. Sci. Comput., 2018, 40: A592-A606

[8] BaiZ-Z, WuW-T. On convergence rate of the randomized Kaczmarz method. Linear Algebra Appl., 2018, 553: 252-269

[9] BaoJ-F, YuCKW, WangJ-H, HuY-H, YaoJ-C. Modified inexact Levenberg-Marquardt methods for solving nonlinear least squares problems. Comput. Optim. Appl., 2019, 74: 547-582

[10] BellaviaS, MoriniB. A globally convergent Newton-GMRES subspace method for systems of nonlinear equations. SIAM J. Sci. Comput., 2001, 23: 940-960

[11] Ben-IsraelA. A Newton-Raphson method for the solution of systems of equations. J. Math. Anal. Appl., 1966, 15: 243-252

[12] BrownKM. A quadratically convergent Newton-like method based upon Gaussian elimination. SIAM J. Numer. Anal., 1969, 6: 560-569

[13] ByrneC. A unified treatment of some iterative algorithms in signal processing and image reconstruction. Inverse Probl., 2004, 20: 103-120

[14] CensorY. Row-action methods for huge and sparse systems and their applications. SIAM Rev., 1981, 23: 444-466

[15] CensorY. Parallel application of block-iterative methods in medical imaging and radiation therapy. Math. Progr., 1988, 42: 307-325

[16] ChenJ-Q, HuangZ-D. On a fast deterministic block Kaczmarz method for solving large-scale linear systems. Numer. Algorithms, 2022, 89: 1007-1029

[17] ChenQ-P, HaoW-R. Randomized Newton’s method for solving differential equations based on the neural network discretization. J. Sci. Comput., 2022, 92: 49

[18] ChenX-J, WomersleyRS. Existence of solutions to systems of underdetermined equations and spherical designs. SIAM J. Numer. Anal., 2006, 44: 2326-2341

[19] DuK, GaoH. A new theoretical estimate for the convergence rate of the maximal weighted residual Kaczmarz algorithm. Numer. Math. Theory Methods Appl., 2019, 12: 627-639

[20] EggermontPPB, HermanGT, LentA. Iterative algorithms for large partitioned linear systems, with applications to image reconstruction. Linear Algebra Appl., 1981, 40: 37-67

[21] ElbleJM, SahinidisNV, VouzisP. GPU computing with Kaczmarz’s and other iterative algorithms for linear systems. Parall. Comput., 2010, 36: 215-231

[22] GordonR, BenderR, HermanGT. Algebraic reconstruction techniques (ART) for three-dimensional electron microscopy and X-ray photography. J. Theor. Biol., 1970, 29: 471-481

[23] GowerRM, RichtárikP. Randomized iterative methods for linear systems. SIAM J. Matrix Anal. Appl., 2015, 36: 1660-1690

[24] HaltmeierM, LeitaoA, ScherzerO. Kaczmarz methods for regularizing nonlinear ill-posed equations I: convergence analysis. Inverse Probl. Imaging, 2007, 1: 289-298

[25] HankeM, NeubauerA, ScherzerO. A convergence analysis of the Landweber iteration for nonlinear ill-posed problems. Numer. Math., 1995, 72: 21-37

[26] HermanGT, MeyerLB. Algebraic reconstruction techniques can be made computationally efficient. IEEE Trans. Med. Imaging, 1993, 12: 600-609

[27] Hounsfield, G.N.: Computerized transverse axial scanning (tomography). Part I. Description of system (Reprinted from British-Journal-of-Radiology. 46, 1016–1022, 1973). Br. J. Radiol. 68, 166–172 (1995)

[28] Kaczmarz, S.: Angenäherte auflösung von systemen linearer gleichungen. Bull. Int. Acad. Polon. Sci. Lett. A 35, 355–357 (1937)

[29] KakAC, SlaneyMPrinciples of Computerized Tomographic Imaging, 1988New YorkIEEE Press

[30] KaltenbacherB, NeubauerA, ScherzerOIterative Regularization Methods for Nonlinear Ill-Posed Problems, 2008BerlinWalter de Gruyter

[31] KelleyCTSolving Nonlinear Equations with Newton’s Method, 2003PhiladelphiaSIAM

[32] KueglerP. A sparse update method for solving underdetermined systems of nonlinear equations applied to the manipulation of biological signaling pathways. SIAM J. Appl. Math., 2012, 72: 982-1001

[33] LiL, LiW-G, XingL-L, BaoW-D. Nonlinear greedy relaxed randomized Kaczmarz method. Results Appl. Math., 2022, 16100340

[34] LiuC-W. An acceleration scheme for row projection methods. J. Comput. Appl. Math., 1995, 57: 363-391

[35] MartínezJM. The projection method for solving nonlinear systems of equations under the “most violated constraint” control. Comput. Math. Appl., 1985, 11: 987-993

[36] McCormickSF. The methods of Kaczmarz and row orthogonalization for solving linear equations and least squares problems in Hilbert space. Indiana Univ. Math. J., 1977, 26: 1137-1150

[37] MeynKH. Solution of underdetermined nonlinear equations by stationary iteration methods. Numer. Math., 1983, 42: 161-172

[38] MoréJJ, GarbowBS, HillstromKE. Testing unconstrained optimization software. ACM Trans. Math. Softw., 1981, 7: 17-41

[39] NeedellD, SrebroN, WardR. Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm. Math. Program., 2016, 155: 549-573

[40] NeedellD, TroppJA. Paved with good intentions: analysis of a randomized block Kaczmarz method. Linear Algebra Appl., 2014, 441: 199-221

[41] NiuY-Q, ZhengB. A greedy block Kaczmarz algorithm for solving large-scale linear systems. Appl. Math. Lett., 2020, 104106294

[42] OrtegaJM, RheinboldtWCIterative Solution of Nonlinear Equations in Several Variables, 1970New YorkAcademic Press

[43] PasqualettiF, CarliR, BulloF. Distributed estimation via iterative projections with application to power network monitoring. Autom. J. IFAC, 2012, 48: 747-758

[44] RomeroLA, MasonJ. Geolocation using TOA, FOA, and altitude information at singular geometries. IEEE Trans. Aerosp. Electron. Syst., 2015, 51: 1069-1078

[45] ShaoC-P. A deterministic Kaczmarz algorithm for solving linear systems. SIAM J. Matrix Anal. Appl., 2023, 44: 212-239

[46] StrohmerT, VershyninR. A randomized Kaczmarz algorithm with exponential convergence. J. Fourier Anal. Appl., 2009, 15: 262-278

[47] Tompkins, C.: Projection methods in calculation. In: Proceedings of the Second Symposium in Linear Programming, Washington, D.C., 1955, pp. 425–448. National Bureau of Standards, Washington, DC (1955)

[48] WangQ-F, LiW-G, BaoW-D, GaoX-Q. Nonlinear Kaczmarz algorithms and their convergence. J. Comput. Appl. Math., 2022, 399113720

[49] YeW-N, ZhangM, ZhuY, WangL-J, HuJ-C, LiX, HuC-X. Real-time displacement calculation and offline geometric calibration of the grating interferometer system for ultra-precision wafer stage measurement. Precis. Eng., 2019, 60: 413-420

[50] YuanR, LazaricA, GowerRM. Sketched Newton-Raphson. SIAM J. Optim., 2022, 32: 1555-1583

[51] ZhangF-Y, BaoW-D, LiW-G, WangQ. On sampling Kaczmarz-Motzkin methods for solving large-scale nonlinear systems. Comput. Appl. Math., 2023, 42: 126

[52] ZhangJ-H, WangY-Q, ZhaoJ. On maximum residual nonlinear Kaczmarz-type algorithms for large nonlinear systems of equations. J. Comput. Appl. Math., 2023, 425115065

Funding

National Natural Science Foundation of China(11871430)

RIGHTS & PERMISSIONS

Shanghai University