Generalized Composed Alternating Relaxed Projection Algorithm for Two-Set Feasibility Problem

1. Problem Statement

The paper addresses the Two-Set Feasibility Problem in a real Hilbert space $\mathcal{H}$. The objective is to find a point $x$ in the intersection of two nonempty, closed, convex sets $X$ and $Y$:
$$\text{find } x \in \mathcal{H} \text{ such that } x \in X \cap Y, \quad \text{where } X \cap Y \neq \emptyset.$$
This problem is fundamental in signal processing, compressed sensing, and image reconstruction. While classical methods like the Method of Alternating Projections (MAP) and Douglas–Rachford (DR) splitting are well-established, they often suffer from slow convergence or undesirable geometric behaviors (e.g., spiraling trajectories) in specific regimes, particularly when $X$ and $Y$ are subspaces with small Friedrichs angles.

2. Methodology: The gCARPA Algorithm

The authors propose the Generalized Composed Alternating Relaxed Projection Algorithm (gCARPA). This algorithm generalizes the recently proposed CARPA (Composed Alternating Relaxed Projection Algorithm) by introducing additional relaxation parameters to control the dynamics between projection and reflection steps.

Core Operators

The algorithm utilizes relaxed reflections defined as:
$$R_X^\theta = (1-\theta)I + \theta(2P_X - I), \quad R_Y^\eta = (1-\eta)I + \eta(2P_Y - I)$$
where $P_X, P_Y$ are orthogonal projections, and $\theta, \eta \in (0, 1]$ are relaxation parameters.

• When $\theta = \eta = 1$, these reduce to standard reflections ($R_X, R_Y$).
• When $\theta = 1/2$, $R_X^\theta$ becomes the projection $P_X$.

Iteration Scheme

The iteration is a fixed-point update $z_{k+1} = F_{\mu, \gamma}^{\theta, \eta}(z_k)$, constructed via an outer averaging step $\mu$ and an internal convex combination controlled by $\gamma$:

1. Relaxed Reflection: $u_{k+1} = R_X^\theta(z_k)$.
2. Projection: $y_{k+1} = P_Y(u_{k+1})$.
3. Relaxed Reflection: $v_{k+1} = R_Y^\eta(u_{k+1})$.
4. Composition: The next iterate is a weighted average of a DR-type term and a projection term:
   $$z_{k+1} = (1-\mu)z_k + \mu \left[ (1-\gamma)\frac{z_k + v_{k+1}}{2} + \gamma y_{k+1} \right]$$
   • $\gamma \in [0, 1)$ controls the blend between DR dynamics ($\gamma=0$) and projection-oriented dynamics ($\gamma=1$).
   • $\mu \in (0, 2/(1+\gamma))$ ensures the operator is averaged.

Non-Stationary Variant (ns-gCARPA)

The paper also introduces a fully non-stationary version where parameters $(\gamma_k, \theta_k, \eta_k)$ vary at each iteration. The parameters are updated such that their increments are summable (e.g., decaying as $O(k^{-(2+\delta)})$), allowing the algorithm to adapt to local geometry while maintaining convergence guarantees.

3. Key Contributions

Theoretical Advances

1. Global Convergence: The authors prove that gCARPA converges weakly to a point in $X \cap Y$ for general closed convex sets. In finite dimensions, convergence is strong. The fixed-point set of the operator is exactly $X \cap Y$ provided $\gamma > 0$.
2. Spectral Characterization for Subspaces: For the case where $X$ and $Y$ are linear subspaces, the authors derive an explicit spectral decomposition using principal angles.
   • They show the convergence rate is governed by the spectral radius of $2 \times 2$ block matrices associated with each principal angle.
   • They derive a minimax parameter selection recipe for the symmetric regime ($\mu=1, \dim X = \dim Y$). By enforcing a "critical damping" condition (discriminant $\Delta = 0$), they identify optimal $\gamma$ values that minimize the worst-case convergence factor over the set of principal angles.
3. Non-Stationary Convergence: They establish that the non-stationary variant converges to the solution set, provided the parameter sequences converge and their deviations are summable.

Practical Insights

• Mitigation of Spiraling: Theoretical analysis and numerical experiments demonstrate that the extra parameters $\theta$ and $\eta$ allow the algorithm to shift the spectrum of the iteration matrix from complex conjugate eigenvalues (causing spiraling) to real eigenvalues (damped approach), significantly improving practical performance.
• Unified Framework: gCARPA unifies several classical methods as special cases, including MAP, DR, RAAR, and CARPA.

4. Results and Numerical Experiments

The paper validates the theory through extensive numerical experiments on three types of problems:

A. Subspace Feasibility

• Linear Convergence: The empirical convergence rates matched the theoretical predictions based on principal angles.
• Performance:
  • Small Angles: CARPA and gCARPA significantly outperformed DR and MAP when the Friedrichs angle was small (nearly parallel subspaces).
  • Large Angles: The generalized gCARPA (with tuned $\theta, \eta$) showed superior performance compared to standard CARPA ($\theta=\eta=1$) in large-angle regimes, reducing the number of iterations required to reach high precision.
  • Trajectory Visualization: Plots confirmed that adjusting $\theta$ and $\eta$ effectively eliminated the spiraling trajectory typical of DR, leading to a more direct path to the intersection.

B. Tangent Ball and Line (Nonlinear Feasibility)

• This problem involves a unit ball and a tangent line, known for causing slow "tail" convergence due to zero angle at the intersection.
• Non-stationarity is Key: Stationary methods (including gCARPA with fixed parameters) performed similarly to DR. However, the non-stationary variant (ns-gCARPA) significantly outperformed all stationary methods at high accuracy tolerances ($10^{-8}, 10^{-10}$), demonstrating that adaptive parameter tuning is crucial for difficult nonlinear geometries.

C. Sparse Linear Inverse Problems (Compressed Sensing)

• Experiments were conducted on finding sparse solutions to underdetermined linear systems ($Ax=b, \|x\|_1 \leq c$).
• Results:
  • gCARPA and ns-gCARPA were competitive with or superior to state-of-the-art methods (GRAP, CARPA) across various sensing models (DCT, Gaussian, etc.).
  • In specific instances (e.g., Problem 3 in the experiments), gCARPA reduced iterations by nearly 3x compared to CARPA.
  • The non-stationary variant provided robustness, often tracking the best-performing curve without manual parameter tuning.

5. Significance

This paper makes a significant contribution to the field of convex optimization and projection methods by:

1. Generalizing State-of-the-Art: It extends the CARPA framework, proving that additional relaxation degrees of freedom ($\theta, \eta$) are not just theoretical curiosities but offer tangible performance gains in specific geometric regimes.
2. Providing a Tuning Recipe: It offers a principled, spectral-based method for selecting parameters to achieve critical damping, moving beyond heuristic tuning.
3. Validating Non-Stationarity: It demonstrates that non-stationary schemes are essential for handling difficult nonlinear feasibility problems where fixed parameters fail to adapt to local geometry.

In summary, gCARPA provides a flexible, robust, and theoretically grounded framework for solving two-set feasibility problems, bridging the gap between the stability of projection methods and the acceleration potential of reflection-based schemes.