Average block nonlinear Kaczmarz methods with adaptive momentum for nonlinear systems of equations
Renjie Ding, Dongling Wang, Jun Zou · 2026
Read Average block nonlinear Kaczmarz methods with adaptive momentum for nonlinear systems of equations by Renjie Ding, Dongling Wang, Jun Zou (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-26381.txt.
Introduction
Ding, Wang, and Zou present momentum-accelerated Kaczmarz methods for large nonlinear systems of equations. The classic Kaczmarz method is prized for its ease and low memory use, but nonlinear versions have lagged behind. Their ABNKAm method averages over blocks and adapts both step sizes and momentum terms on the fly. It needs few inner products per step, which keeps cost and memory low. They prove fast convergence to the nearest solution, and tests show it beats prior nonlinear variants.
Catalog record
| CREATOR | Renjie Ding, Dongling Wang, Jun Zou |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 76139 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.26381
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Average block nonlinear Kaczmarz methods with adaptive momentum for nonlinear systems of equations Thanks: Submitted to the editors DATE. Renjie Ding, Dongling Wang, Jun Zou Abstract The Kaczmarz method is widely recognized as an efficient iterative algorithm for solving large-scale linear systems, owing to its simplicity and low memory requirements. However, the development of its nonlinear extensions for solving large-scale nonlinear systems has seen limited progress. In this work, we introduce a new family of momentum-accelerated averaging block nonlinear Kaczmarz methods tailored for large-scale nonlinear systems and ill-posed problems. Our contributions are twofold: (1) We develop an adaptive strategy for selecting step sizes and momentum coefficients, leading to a new average block nonlinear Kaczmarz method with adaptive momentum (ABNKAm). This algorithm achieves high computational efficiency by requiring only minimal inner-product computations per iteration, which significantly reduces both arithmetic complexity and memory usage. (2) We establish rigorous convergence of the ABNKAm under mild assumptions, proving that the method converges exponentially to the unique solution nearest to the initial point. Moreover, under suitable conditions, we provide a theoretical justification of acceleration of the proposed ABNKAm with momentum. Extensive numerical experiments demonstrate that ABNKAm outperforms existing nonlinear Kaczmarz variants in terms of both iteration count and computational time, with particularly notable gains in large-scale problems. keywords Nonlinear systems, the averaging block nonlinear Kaczmarz method, heavy ball momentum, adaptive strategy Funding. The work of D. Wang was partially supported by National Natural Science Foundation of China under grants 12271463. The work of J. Zou was substantially supported by Hong Kong RGC General Research Fund (projects 14306623 and 14308322) and NSFC/Hong Kong RGC Joint Research Scheme (project N_CUHK465/22). † † runningheads: Nonlinear Kaczmarz methods for nonlinear systems / R. Ding, D. Wang, and J. Zou MSC 65H10, 90C06 1 Introduction Consider solving the following system of nonlinear equations: F(x)=0, (1) where F:\mathbb{R}^{n}\rightarrow\mathbb{R}^{m} is a nonlinear vector-valued function and x\in\mathbb{R}^{n} is an unknown vector. The system of nonlinear equations F can be rewritten in component form as F_{i} for i=1,\cdots,m , where F_{i}:\mathbb{R}^{n}\rightarrow\mathbb{R} denotes the i -th component of F . Solving large-scale systems of the form ( 1 ) arises widely and significantly in applications such as electrical impedance tomography, circuit design, nonlinear programming [ 15 ] , systems of nonlinear differential equations [ 27 ] , and machine learning [ 5 , 16 , 19 ] . Therefore, the efficient solution of the large-scale system of nonlinear equations ( 1 ) is of utmost importance. Classical iterative methods, such as Newton-type methods, are widely used but often entail high computational costs or become inapplicable for large-scale or ill-conditioned problems. Thus, there is a pressing need for efficient, low-cost iterative methods. For the solution of large-scale linear systems, the Kaczmarz algorithm [ 14 , 33 ] , as a low cost and efficient algorithm, has been remarkably developed. When F=Ax-b , where A\in\mathbb{R}^{m\times n} and b\in\mathbb{R}^{m} , the Kaczmarz method orthogonally projects the current iteration point x_{k} onto the constraint set \{x|A_{i_{k}}x=b_{i_{k}}\} , namely it updates the iteration as x_{k+1}=x_{k}-\frac{A_{i_{k}}x_{k}-b_{i_{k}}}{\|A_{i_{k}}\|_{2}^{2}}(A_{i_{k}})^{T}, (2) where the index i_{k} is selected via random or cyclic sampling from [m]:=\{1,\dots,m\} . This approach significantly reduces the computational cost and storage requirements per iteration. The Kaczmarz method was extended for solving large-scale nonlinear systems [ 35 ] , with a family of nonlinear Kaczmarz algorithms. These include the nonlinear Kaczmarz (NK), the nonlinear randomized Kaczmarz (NRK), and the nonlinear uniformly randomized Kaczmarz (NURK) methods. Notably, they established a connection between the NURK method and the stochastic gradient descent (SGD) method [ 13 , 31 ] . These methods are based on the following iterative scheme: \displaystyle x_{k+1}=x_{k}-\frac{F_{i_{k}}(x_{k})}{\|\nabla F_{i_{k}}(x_{k})\|^{2}_{2}}\nabla F_{i_{k}}(x_{k}). (3) Here \nabla F_{i_{k}}(x) denotes the gradient function of F_{i_{k}}(x) . However, selecting index sets from [m] via random or cyclic order strategies may be inefficient and may lead to the selection of indices corresponding to small residual values. To address this limitation, several approximate greedy strategies have been proposed [ 21 , 25 , 40 , 41 ] , which first construct a controlled index subset \mathcal{J}_{k} and then select an index from \mathcal{J}_{k} based on given probability. To further accelerate the convergence of the NK method, a relaxation parameter \alpha in the iterative formula ( 3 ) is introduced in [ 20 ] to enhance convergence. Specifically, the proposed iteration scheme is formulated as: \displaystyle x_{k+1}=x_{k}-\alpha\frac{F_{i_{k}}(x_{k})}{\|\nabla F_{i_{k}}(x_{k})\|^{2}_{2}}\nabla F_{i_{k}}(x_{k}). (4) The Nonlinear Greedy Randomized Kaczmarz method with momentum (NGRKm), integrating a Polyak heavy ball momentum [ 29 ] into the NGRK framework, was further developed in [ 21 ] : x_{k+1}=x_{k}-\alpha\frac{F_{i_{k}}(x_{k})}{\|\nabla F_{i_{k}}(x_{k})\|^{2}_{2}}\nabla F_{i_{k}}(x_{k})+\beta(x_{k}-x_{k-1}), (5) where \alpha and \beta are the step size and momentum parameter, respectively. Numerical experiments demonstrated the accelerance of NGRKm over NGRK [ 21 ] . Although the above methods have shown improvements over the classical nonlinear Kaczmarz method, they suffer from two significant drawbacks: (i) The selection of relaxation parameters \alpha and momentum parameters \beta lacks theoretical guidance. (ii) These methods update the solution in each iteration by exploiting the knowledge from just a single equation. Compared with the block method to be introduced below, which updates the approximation by leveraging information from a set of equations at each iteration, this inherent limitation causes their convergence rate to deteriorate substantially as the problem scale increases. This will be demonstrated clearly through several typical examples numerically in Section 4 . With respect to the drawback (i), there are many interesting and in-depth studies [ 1 , 22 , 24 , 32 , 39 , 6 ] for the linear Kaczmarz method for linear systems. In particular, an adaptive stochastic heavy-ball momentum method was developed in [ 39 ] , with a significant feature that the choice of the momentum parameter is independent of the singular values of the coefficient matrix. However, to the best of our knowledge, there is still no similar efficient algorithm available for the nonlinear Kaczmarz method. Building on the success of the linear block Kaczmarz method [ 9 , 4 , 25 , 26 , 30 ] , which has demonstrated superiority in handling large-scale linear systems, some studies have extended the concept to the nonlinear equations and developed a nonlinear block Kaczmarz method [ 34 , 40 , 41 , 37 ] . This approach utilizes multiple equations simultaneously in each iteration, with the iterative formula defined as \displaystyle x_{k+1}=x_{k}-(F_{\mathcal{J}_{k}}^{\prime}(x_{k}))^{\dagger}F_{\mathcal{J}_{k}}(x_{k}), (6) where F_{\mathcal{J}_{k}}^{\prime}(x_{k})^{\dagger} denotes the Moore-Penrose pseudo-inverse of the submatrix of F^{\prime}(x_{k}) and the block index set \mathcal{J}_{k}\subset[m] . Notably, the maximum-residual block nonlinear Kaczmarz method (MRBNK) can also be regarded as an iterative sketch-and-project method applied to the sketched Newton system [ 38 , 40 ] . However, these methods require the computing of the Moore-Penrose pseudoinverse of the sub-matrix of the Jacobian matrix in each iteration, which increases the computational cost of the methods. To avoid computing the pseudoinverse, a variation of the block Kaczmarz method was proposed by first projecting the current iterate onto each row of the selected block matrix, then computing the next iterate as a convex combination of these projections: \displaystyle x_{k+1}=x_{k}-\alpha_{k}\left(\sum_{i\in\mathcal{J}_{k}}\omega_{k}^{(i)}\frac{F_{i}(x_{k})}{\|\nabla F_{i}(x_{k})\|^{2}}\nabla F_{i}(x_{k})\right),k\geq 0, (7) where the weights \omega_{k}^{(i)}\in[0,1] and satisfy \sum_{i\in\mathcal{J}_{k}}\omega_{k}^{(i)}=1 and \alpha_{k}\in(0,2) . The method constructed based on iterative formula ( 7 ) is named