🔢 mathematics

Average block nonlinear Kaczmarz methods with adaptive momentum for nonlinear systems of equations

This paper introduces the Average Block Nonlinear Kaczmarz method with Adaptive Momentum (ABNKAm), a new iterative algorithm for large-scale nonlinear systems that employs an adaptive strategy for step sizes and momentum coefficients to achieve rigorous exponential convergence and superior computational efficiency compared to existing variants.

Original authors: Renjie Ding, Dongling Wang, Jun Zou

Published 2026-03-30

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Renjie Ding, Dongling Wang, Jun Zou

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to find the perfect spot to park your car in a massive, chaotic parking lot (the Nonlinear System). You don't have a map, and the lot is so huge that checking every single spot one by one would take forever. This is the problem scientists face when solving complex equations in fields like medical imaging, circuit design, or machine learning.

For decades, the standard way to solve this was the Kaczmarz Method. Think of this as a driver who, at every turn, picks one random parking line, checks if they are aligned with it, and makes a tiny adjustment. It's simple and doesn't require much memory, but it's slow. If the lot is huge, the driver might zigzag for hours before finding the spot.

Recently, smarter drivers started using Block Methods. Instead of checking one line, they check a whole row of lines at once. This is faster, but calculating the perfect adjustment for a whole row is computationally expensive, like trying to solve a complex math puzzle in your head while driving.

The New Solution: The "Smart Navigator" (ABNKAm)

The paper you provided introduces a new algorithm called ABNKAm (Average Block Nonlinear Kaczmarz with Adaptive Momentum). Here is how it works, using some everyday analogies:

1. The "Block" Strategy (Checking a Row, Not a Spot)

Instead of looking at just one equation (one parking line), the new method looks at a group of equations at once.

Analogy: Imagine you are painting a wall. The old way was to paint one tiny square, stop, measure, and paint the next. The "Block" way is to grab a wide roller and paint a whole strip at once. It covers more ground per step.

2. The "Averaging" Trick (The Cheap Shortcut)

Usually, when you look at a whole group of lines, calculating the perfect move is hard (it requires a "pseudoinverse," which is like doing advanced calculus in your head).

Analogy: The authors found a shortcut. Instead of solving the hard math for the whole group, they take a weighted average of the individual adjustments. It's like asking five friends for directions, taking the average of their advice, and moving that way. It's much faster to calculate and doesn't require a supercomputer, but it's not perfectly precise on its own.

3. The "Momentum" Boost (The Heavy Ball)

This is the secret sauce. In physics, if you roll a heavy ball down a hill, it builds up speed and doesn't stop immediately when the terrain gets rough. It keeps rolling forward due to momentum.

Analogy: Previous methods were like a hiker who stops at every step to check a compass. They are careful but slow. The ABNKAm method is like a skier. If they were moving fast in a certain direction last turn, they use that speed to carry them forward, even if the path gets a little bumpy. This helps them skip over small obstacles and reach the solution much faster.

4. The "Adaptive" Brain (No Manual Tuning)

The biggest problem with "momentum" in the past was that you had to guess how much momentum to use. Too little, and you go slow; too much, and you crash.

Analogy: Imagine driving a car with a cruise control that adjusts itself automatically based on the road. If the road is smooth, it speeds up. If it gets bumpy, it slows down. The ABNKAm method does this automatically. It looks at where it just was and where it is now, and it calculates the perfect amount of momentum for the next step on the fly. You don't need to fiddle with knobs or guess numbers; the algorithm figures it out itself.

Why Does This Matter?

The authors tested this "Smart Navigator" on some of the hardest parking lots imaginable (huge, complex math problems).

Speed: It found the solution in far fewer steps than the old methods.
Efficiency: It didn't need a supercomputer to do the math; it ran fast on standard laptops.
Reliability: In some tests, the old methods got stuck in a loop (oscillating back and forth) and never found the solution. The new method, thanks to its momentum, broke out of the loop and found the answer.

The Bottom Line

The paper presents a new way to solve massive, messy math problems. It combines checking multiple clues at once (Block), taking a quick average (Averaging), and using built-up speed to keep moving forward (Momentum), all while automatically adjusting its own speed (Adaptive).

It's like upgrading from a driver who checks one GPS signal at a time to a self-driving car that scans the whole road, uses its momentum to glide over bumps, and constantly recalibrates its route to get you home in record time.

1. Problem Statement

The paper addresses the challenge of solving large-scale systems of nonlinear equations of the form:
$F(x) = 0$
where $F: \mathbb{R}^n \to \mathbb{R}^m$ is a nonlinear vector-valued function.

Context: These systems arise in critical applications such as electrical impedance tomography, circuit design, and machine learning.
Limitations of Existing Methods:
- Classical Iterative Methods (e.g., Newton-type): Often too computationally expensive or memory-intensive for large-scale or ill-conditioned problems.
- Nonlinear Kaczmarz Variants (NK, NRK, NGRKm): While efficient, single-equation update strategies (row-action methods) suffer from slow convergence as problem scales increase.
- Block Methods (e.g., MRBNK): Update using subsets of equations but often require computing the Moore-Penrose pseudoinverse of sub-Jacobian matrices, which is computationally costly.
- Averaging Block Methods (ABNK): Avoid pseudoinverses by averaging projections but often lack theoretical guidance for parameter selection (step size, momentum) and may have slower convergence rates.

2. Methodology

The authors propose a new family of algorithms called Average Block Nonlinear Kaczmarz with Adaptive Momentum (ABNKAm).

A. General Framework (ABNKm)

The method combines block averaging with momentum acceleration. The general iterative scheme is:
$x_{k+1} = x_k - \alpha_k \left( \sum_{i \in J_k} \omega_k^{(i)} \frac{F_i(x_k)}{\|\nabla F_i(x_k)\|^2} \nabla F_i(x_k) \right) + \beta_k (x_k - x_{k-1})$

Block Selection ( $J_k$ ): Uses a greedy criterion to select a subset of indices with large residuals: $J_k = \{ i \mid |F_i(x_k)|^2 \geq \theta \max_j |F_j(x_k)|^2 \}$ .
Averaging: Instead of a pseudoinverse, it computes a weighted average of projections onto the selected equations.
Momentum: Incorporates a Polyak heavy ball term $\beta_k (x_k - x_{k-1})$ to accelerate convergence.

B. Adaptive Strategy (ABNKAm)

The core innovation is an adaptive strategy for selecting the step size ( $\alpha_k$ ) and momentum coefficient ( $\beta_k$ ) without manual tuning or knowledge of the true solution $x^*$ .

Optimization Goal: The parameters are derived by minimizing the error $\|x_{k+1} - x^*\|^2$ subject to the update rule.
Approximation: Since $x^*$ $x^{*}$ is unknown, the authors use:
- Orthogonality: $\langle x_k - x_{k-1}, x_k - x^* \rangle = 0$ (derived from geometric projection properties).
- Linearization: Approximating $\langle d_k, x_k - x^* \rangle$ using a first-order Taylor expansion of $F$ .
Closed-Form Solution: This yields explicit formulas for $\alpha_k$ and $\beta_k$ based solely on current iterates and gradients.
Robustness (Algorithm 2.2): A hybrid implementation is proposed. If the adaptive parameters lead to numerical instability (e.g., $\Delta_k \approx 0$ or $\beta_k$ out of bounds), the algorithm reverts to a standard adaptive step size with zero momentum for that iteration.

3. Key Contributions

Novel Algorithm (ABNKAm): A unified framework integrating block averaging, greedy selection, and adaptive momentum. It generalizes existing methods like ABNK and NGRKm as special cases.
Adaptive Parameter Selection: A theoretical derivation for step sizes and momentum coefficients that requires no manual tuning and no knowledge of the true solution. This overcomes a major limitation of previous momentum-based Kaczmarz methods.
Computational Efficiency: The method requires only minimal inner-product computations per iteration (at most 4 vector inner products) and avoids the expensive computation of matrix pseudoinverses.
Rigorous Convergence Analysis:
- Proved exponential convergence to the unique minimum-norm solution nearest to the initial point under mild assumptions (local tangential cone condition).
- Demonstrated theoretically that the convergence rate of ABNKAm is strictly faster than the non-momentum ABNK variant.
Scalability: The method is designed specifically for large-scale and ill-posed problems where traditional block methods fail due to memory or cost constraints.

4. Numerical Results

The authors tested ABNKAm on five diverse nonlinear problems (Modified Rosenbrock, Extended Cragg Levy, Chandrasekhar H-equation, Augmented Rosenbrock, and Extended Powell Badly Scaled) with dimensions up to $m = 10^6$ .

Performance Metrics: Compared Iteration Count (IT) and CPU Time against ABNK2, RB-CNK, MRBNK, NGRKm, MRNK, and NURK.
Key Findings:
- Superior Speed: ABNKAm consistently required the fewest iterations and least CPU time across all test cases.
- Scalability: The speed-up ratio (SU) of ABNKAm over competitors increased with problem size. For example, on the Modified Rosenbrock problem ( $m=10^6$ ), ABNKAm was 713x faster than ABNK2 and 16x faster than MRBNK.
- Robustness: ABNKAm was the only method to successfully converge on the "Extended Powell Badly Scaled" problem, where all other methods (including block methods) failed or oscillated indefinitely.
- Momentum Effect: In problems like the Chandrasekhar H-equation, the momentum parameter $\beta_k$ became non-zero after the first few iterations, significantly accelerating the descent compared to the momentum-free ABNK2.

5. Significance

Bridging the Gap: This work successfully extends the efficiency of linear Kaczmarz methods (specifically the heavy ball momentum and adaptive strategies) to the nonlinear domain, a field where progress has been limited.
Practical Impact: By eliminating the need for pseudoinverses and manual parameter tuning, ABNKAm offers a "plug-and-play" solution for large-scale nonlinear inverse problems and optimization tasks.
Theoretical Advancement: The paper provides a rigorous proof that adaptive momentum can theoretically guarantee faster convergence rates than standard block averaging, validating the empirical success of momentum in stochastic and iterative settings.
Future Direction: The authors suggest that developing specialized greedy criteria tailored to the ABNKAm framework is a promising avenue for further research.