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

1. Problématique

L'article s'intéresse au problème de faisabilité à deux ensembles dans un espace de Hilbert réel $H$. L'objectif est de trouver un point $x$ appartenant à l'intersection de deux ensembles convexes fermés non vides $X$ et $Y$ ($X \cap Y \neq \emptyset$) :
$$\text{trouver } x \in H \text{ tel que } x \in X \cap Y.$$
Ce type de problème est fondamental dans de nombreuses applications telles que le traitement du signal et d'images, la détection compressée (compressed sensing) et le traitement des données sismiques.

Les méthodes basées sur la projection, comme la méthode des projections alternées (MAP) et l'algorithme de Douglas-Rachford (DR), sont couramment utilisées. Cependant, la méthode DR, bien que possédant de bonnes propriétés théoriques, peut présenter un comportement de spirale prononcé (trajectoire tournoyante) sur les problèmes de sous-espaces, ce qui ralentit la convergence pratique. L'algorithme CARPA (proposé récemment par Shen et al.) a tenté de résoudre ce problème en mélangeant des dynamiques de type DR et des corrections de type projection-réflexion, mais l'article vise à aller plus loin en introduisant une flexibilité supplémentaire.

2. Méthodologie : l'algorithme gCARPA

Les auteurs proposent un nouvel algorithme appelé gCARPA (Generalized Composed Alternating Relaxed Projection Algorithm). Il s'agit d'une généralisation de CARPA qui introduit des paramètres de relaxation supplémentaires pour mieux contrôler la dynamique de l'itération.

Définition des opérateurs :
L'algorithme utilise des réflexions relâchées sur les deux ensembles $X$ et $Y$ :
$$R^\theta_X = (1-\theta)I + \theta(2P_X - I)$$
$$R^\eta_Y = (1-\eta)I + \eta(2P_Y - I)$$
où $P_X$ et $P_Y$ sont les projections orthogonales, et $\theta, \eta \in (0, 1]$ sont des paramètres de relaxation.

• Si $\theta = \eta = 1$, on retrouve les réflexions standards de CARPA.
• Si $\theta = 1/2$, $R^\theta_X$ devient la projection $P_X$.

Schéma itératif :
L'algorithme génère une suite $\{z_k\}$ via une combinaison convexe d'un terme de type Douglas-Rachford et d'un terme de projection :
$$z_{k+1} = (1-\mu)z_k + \mu \left[ (1-\gamma) A_{\theta,\eta}(z_k) + \gamma B_\theta(z_k) \right]$$
où :

• $A_{\theta,\eta} = \frac{1}{2}(I + R^\eta_Y R^\theta_X)$ (terme de type DR).
• $B_\theta = P_Y R^\theta_X$ (terme de type projection-réflexion).
• $\gamma \in [0, 1)$ contrôle le mélange entre les deux dynamiques.
• $\mu \in (0, 2/(1+\gamma))$ est un paramètre de relaxation externe.

Variante non stationnaire (ns-gCARPA) :
Les auteurs introduisent également une version où les paramètres $(\gamma_k, \theta_k, \eta_k)$ varient à chaque itération. Cette variante permet d'adapter l'algorithme à la géométrie locale du problème, en assurant que les variations de paramètres sont sommables pour garantir la convergence.

3. Contributions Clés

1. Unification et Généralisation :

   • gCARPA englobe plusieurs méthodes classiques comme cas particuliers : MAP, DR, CARPA, GRAP, RAAR, etc.
   • L'introduction des paramètres $\theta$ et $\eta$ offre des degrés de liberté supplémentaires pour équilibrer la rotation (spirale) et l'amortissement dans la dynamique des points fixes.

2. Convergence Globale :

   • Sous des hypothèses standards (ensembles convexes fermés, intersection non vide), l'article prouve la convergence faible de la suite $\{z_k\}$ vers un point dans $X \cap Y$.
   • En dimension finie, la convergence est forte.
   • La convergence de la variante non stationnaire est établie en traitant les variations de paramètres comme des perturbations sommables d'une application moyenne fixe.

3. Caractérisation Spectrale pour les Sous-espaces :

   • Pour le cas où $X$ et $Y$ sont des sous-espaces linéaires, les auteurs dérivent une caractérisation spectrale explicite basée sur les angles principaux entre les sous-espaces.
   • Ils obtiennent des formules pour les facteurs de convergence linéaire (module des valeurs propres dominantes).
   • Ils proposent une recette minimax pour sélectionner le paramètre $\gamma$ de manière optimale dans un régime symétrique, visant un amortissement critique sur les plans d'angles principaux.

4. Analyse Numérique et Performance :

   • Des expériences montrent que les paramètres de relaxation supplémentaires ($\theta, \eta$) peuvent réduire le nombre d'itérations par rapport à CARPA et DR, en particulier pour des angles de Friedrichs plus grands ou dans des géométries spécifiques.
   • La variante non stationnaire (ns-gCARPA) démontre une robustesse accrue, notamment pour les problèmes non linéaires difficiles (ex: intersection d'une boule et d'une tangente) où les paramètres fixes échouent souvent.

4. Résultats Principaux

• Sur les sous-espaces :

  • Les simulations confirment que le taux de convergence linéaire prédit par la théorie spectrale correspond aux taux empiriques observés.
  • La méthode gCARPA, avec un réglage optimal de $(\theta, \eta, \gamma)$, peut surpasser CARPA (qui correspond à $\theta=\eta=1$) en réduisant davantage le facteur de contraction spectral, notamment pour des angles intermédiaires à grands.
  • La visualisation des trajectoires montre que gCARPA atténue efficacement le comportement spiralé de DR, passant d'une dynamique à valeurs propres complexes (rotation) à une dynamique à valeurs propres réelles (amortissement).

• Sur les problèmes non linéaires (Boule tangente à une droite) :

  • Ce problème est connu pour sa convergence lente due à l'angle nul à l'intersection.
  • Les méthodes stationnaires (MAP, DR, CARPA fixe) montrent une phase de queue très lente.
  • Les méthodes non stationnaires (ns-DR, ns-CARPA, ns-gCARPA) surclassent largement les versions stationnaires.
  • ns-gCARPA est particulièrement performant aux tolérances élevées, réduisant le nombre d'itérations de manière significative par rapport à ns-CARPA, ce qui suggère que l'adaptation dynamique de $\theta$ et $\eta$ aide à surmonter le ralentissement près du point de tangence.

• Sur les problèmes inverses linéaires parcimonieux (Compressed Sensing) :

  • Sur des instances réalistes de reconstruction de signaux, gCARPA et ns-gCARPA sont compétitifs, voire supérieurs, aux méthodes de référence (CARPA, GRAP).
  • L'avantage de gCARPA est particulièrement visible sur certaines géométries de capteurs (ex: Problème 3 dans l'article), où les paramètres de relaxation supplémentaires permettent une convergence plus rapide.

5. Signification et Impact

Cet article apporte une contribution significative à la théorie et à la pratique des algorithmes de projection pour les problèmes de faisabilité convexe :

• Théorique : Il fournit une compréhension plus profonde de la relation entre les paramètres de relaxation et la géométrie des angles principaux, offrant des outils pour le réglage optimal des paramètres (recette minimax).
• Pratique : Il démontre que l'ajout de degrés de liberté via la relaxation des réflexions ($\theta, \eta$) n'est pas seulement une généralisation théorique, mais un levier pratique pour améliorer la vitesse de convergence et la robustesse, surtout dans des régimes où les méthodes classiques (DR, MAP) ou même CARPA standard montrent des limites.
• Innovation : La variante non stationnaire propose une approche adaptative efficace pour les problèmes complexes où la géométrie locale varie le long de la trajectoire de convergence, évitant ainsi le besoin de choisir manuellement des paramètres fixes optimaux.

En résumé, gCARPA représente une évolution puissante des méthodes de projection alternées, combinant la stabilité des méthodes de type Douglas-Rachford avec la précision des méthodes de projection, tout en offrant une flexibilité paramétrique supérieure pour accélérer la convergence.