🔢 mathematics

A residual-iteration framework for alternating projections between affine subspaces

This paper reformulates alternating projections between affine subspaces as a least-squares minimization problem, establishing a unified residual-iteration framework that enables the derivation of accelerated variants (such as steepest descent and conjugate gradient) with rigorous convergence guarantees expressed in terms of geometric angles between the subspaces.

Original authors: Nguyen T. Thao

Published 2026-07-15

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Nguyen T. Thao

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 a hidden treasure chest in a vast, infinite room. The chest is located exactly where two invisible, flat walls (let's call them Wall U and Wall W) cross each other. If the walls actually touch, the treasure is right there. But what if the walls are parallel and never meet? In that case, the treasure is the spot on Wall U that is closest to Wall W.

For decades, mathematicians have used a simple game called "Alternating Projections" to find this spot. The game is easy: you stand on Wall U, walk straight over to Wall W, then turn around and walk straight back to Wall U, and repeat. You bounce back and forth like a pinball.

In this paper, Nguyen T. Thao reveals a secret: this bouncing game is actually just a very specific, slightly clumsy way of solving a math puzzle called "Least Squares." Think of the Least Squares problem as trying to fit a straight line through a messy cloud of data points. The "bouncing" method is actually just a "gradient descent" algorithm (a way of sliding down a hill to find the lowest point) that takes tiny, fixed-size steps.

The Big Discovery: A New Toolkit
The author's main finding is that by realizing the "bouncing game" is just a math puzzle, we can swap the clumsy, fixed-step bouncing for much smarter, faster ways to solve the puzzle. The paper introduces a "residual-iteration framework." Imagine this as a new set of tools that can take any standard math solver and turn it into a new, super-charged version of the wall-bouncing game.

The paper proves that three specific tools work perfectly in this new framework:

Landweber Iteration: The original "bouncing" method, but with adjustable step sizes.
Steepest Descent: A method that looks at the slope of the hill and takes the biggest possible step downhill at every turn.
Conjugate Gradient: The "smartest" tool, which remembers its past steps to zigzag efficiently toward the goal, avoiding the back-and-forth wobble.

What the Paper Says About Steepest Descent
The paper is very careful about what it claims. It proves that if the "walls" (subspaces) are arranged in a specific way (mathematically, if the "Friedrichs angle" between them is positive), these new methods will definitely converge to the right answer.

However, regarding the "Steepest Descent" method, the paper notes a subtle but important distinction. While the method works great when a solution exists, the paper states that proving it works perfectly in every possible scenario (specifically, when the solution set is non-empty but the math is messy) remains an open question or a "conjecture." The paper does not argue that it fails; rather, it admits that a complete mathematical proof for the most general case is not yet established, so it restricts its guaranteed claims to scenarios with stricter conditions (like closed ranges).

How Fast Do They Go?
The paper doesn't just say "it's faster"; it gives exact formulas for how fast. It turns out the speed depends on the "angles" between the walls.

If the walls are almost parallel (a very small angle), the original bouncing method is incredibly slow.
The new "Steepest Descent" and "Conjugate Gradient" versions are proven to be significantly faster.
The paper provides a specific formula for the speed: it depends on a ratio called $\kappa$ (kappa), which is the ratio of the largest angle to the smallest angle between the walls. The Conjugate Gradient method is shown to have a convergence rate of $1 - \frac{2}{\kappa + 1}$ , which is strictly better (faster) than the Steepest Descent rate of $1 - \frac{2}{\kappa^2 + 1}$ . (Note: Since $\kappa > 1$ , the term $\frac{2}{\kappa+1}$ is larger than $\frac{2}{\kappa^2+1}$ , making the subtraction larger and the remaining rate smaller, which means faster convergence).

The "Inconsistent" Case
What if the walls never touch? The paper shows that these new methods handle this gracefully too. If no solution exists, the "bouncing" doesn't just get stuck; the distance you walk grows infinitely large, which is a clear signal that the walls are parallel and you need to stop looking for an intersection. This behavior is proven mathematically for all three methods.

The Bottom Line
This paper doesn't just tweak the old method; it rewrites the rules. By viewing the problem as a least-squares optimization task, the author proves that we can use powerful, existing math tools to make the "wall-bouncing" game much more efficient. The results are mathematically proven (not just simulated) for a wide range of scenarios, offering a clear path to faster solutions in both consistent (walls touch) and inconsistent (walls miss) situations. The "Conjugate Gradient" version is highlighted as the champion, offering the fastest theoretical speed, while the "Steepest Descent" version offers a solid middle ground. The paper leaves the door open for even more advanced tools (like "quasi-Newton" methods) to be added to this toolkit in the future.

Technical Summary: A Residual-Iteration Framework for Alternating Projections Between Affine Subspaces

Problem Statement
The paper addresses the problem of finding an element in the intersection of two closed affine subspaces, $U$ and $W$ , within a Hilbert space $(H, \|\cdot\|)$ . When the intersection is non-empty, the classical algorithm involves alternating orthogonal projections ( $u^{(n+1)} = P_U P_W u^{(n)}$ ). When the intersection is empty (the inconsistent case), the standard iteration is known to converge to a point in $U$ closest to $W$ , provided such a point exists. The primary objective of this work is to reformulate this problem to enable the development of accelerated alternating projection algorithms with rigorous convergence guarantees in both consistent and inconsistent settings.

Methodology
The core methodological contribution is the reformulation of alternating projections as the minimization of a least-squares functional associated with a bounded linear operator.

Least-Squares Reformulation: The author demonstrates that the alternating projection iteration is equivalent to a gradient descent iteration with unit step size for the functional $\Phi_{U,W}(u) = \frac{1}{2}\|u - P_W u\|^2$ . By defining a bounded linear operator $Q: U \to V^\perp$ (where $V$ is the direction subspace of $W$ ) and a vector $w = P_W 0$ , the problem is transformed into minimizing $\Phi_{Q,w}(u) = \frac{1}{2}\|Qu - w\|^2$ .
Residual-State Iteration Framework: A general framework of "admissible residual-state iterations" is introduced. This framework encompasses various optimization algorithms (Landweber, steepest descent, conjugate gradient) by defining iterations based on the evolution of residuals $r^{(n)} = Q^*(Qu^{(n)} - w)$ and a state variable $s^{(n)}$ .
Abstract Convergence Principles: The paper establishes two key abstract properties to guarantee strong convergence (convergence in norm):
- Residual Extinction: The condition that the residual sequence $r^{(n)}$ converges to zero.
- Translation Equivariance: A property ensuring that the behavior of the iteration is invariant under specific translations of the initial iterate and the target vector. This allows convergence results derived for the zero-initial-iterate case to be transferred to arbitrary initial iterates.

Key Contributions and Results

Unification of Methods: The paper proves that classical alternating projections are exactly the unit-step Landweber iteration. It extends this to include steepest-descent and conjugate-gradient (CG) variants as natural accelerations within the same framework.
Strong Convergence Guarantees:
- Landweber Iteration: Strong convergence is established for any sequence of relaxation coefficients satisfying specific summability conditions, covering both consistent ( $M_{Q,w} \neq \emptyset$ ) and inconsistent ( $M_{Q,w} = \emptyset$ ) cases. In the inconsistent case, the iterates diverge in norm, characterizing the intrinsic behavior when no least-squares solution exists.
- Steepest Descent: The paper provides a partial strong convergence result, noting that full convergence under the sole condition $M_{Q,w} \neq \emptyset$ remains a conjecture in the literature, though it is proven under stronger conditions (e.g., when the range of $Q$ is closed).
- Conjugate Gradient: Strong convergence is established for the CG method under the condition $M_{Q,w} \neq \emptyset$ , utilizing the fact that CG minimizes the functional over expanding Krylov subspaces.
Linear Convergence and Rates: Under the assumption that the range of $Q$ $Q$ is closed (equivalent to the Friedrichs angle $\theta_f$ $θ_{f}$ between the subspaces being positive), the paper derives explicit linear convergence rates.
- The convergence rates are expressed in terms of the condition number $\kappa = \|Q\|/\gamma(Q)$ , where $\gamma(Q)$ is the reduced minimum modulus.
- Geometrically, $\|Q\|$ relates to the largest principal angle $\theta_p$ ( $\|Q\| = \sin \theta_p$ ), and $\gamma(Q)$ relates to the Friedrichs angle ( $\gamma(Q) = \sin \theta_f$ ).
- The paper provides explicit bounds for the error decay:
  - Landweber: $\|e^{(n)}\| \leq (1 - \epsilon/\kappa^2)^n \|e^{(0)}\|$ .
  - Steepest Descent: $\|e^{(n)}\| \leq \kappa (1 - \frac{2}{\kappa^2+1})^n \|e^{(0)}\|$ .
  - Conjugate Gradient: $\|e^{(n)}\| \leq 2\kappa (1 - \frac{2}{\kappa+1})^n \|e^{(0)}\|$ .
Comparison of Rates: The analysis confirms the theoretical advantage of CG over steepest descent, which in turn outperforms the basic Landweber iteration (classical alternating projections), particularly when $\kappa > 1$ .

Significance and Claims
The paper claims to provide a unified theoretical framework that separates the analysis of optimization algorithms from their geometric interpretation as projections. By establishing that alternating projections are a specific instance of least-squares minimization, the author enables the direct transfer of convergence properties from well-studied optimization methods to projection algorithms.

The significance lies in:

Generalization: Moving beyond constant relaxation parameters to varying relaxation coefficients and different optimization strategies (steepest descent, CG) while maintaining rigorous convergence proofs.
Handling Inconsistency: Providing a clear characterization of algorithm behavior when the intersection of subspaces is empty, distinguishing between convergence to a best approximation and divergence.
Quantitative Analysis: Offering explicit linear convergence rates in infinite-dimensional settings based on the geometric angles between subspaces, a level of detail that numerical experimentation alone cannot capture.
Algebraic Insight: The paper highlights that restricting the initial iterate to the subspace $U$ allows for a self-adjoint formulation ( $L_\alpha$ ) that simplifies the analysis of convergence rates compared to the general case involving non-self-adjoint operators ( $F_\alpha$ ).

The work concludes that this optimization-based perspective offers a general methodology for constructing and analyzing alternating projection methods, suggesting future applications to other optimization techniques such as quasi-Newton methods and regularization strategies.

More like this