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

Titolo: Algoritmo Generalizzato di Proiezione Alternata Rilassata Composta per Problemi di Feasibilità a Due Insiemi

1. Il Problema

Il lavoro affronta il problema di fattibilità a due insiemi in uno spazio di Hilbert reale $\mathcal{H}$. L'obiettivo è trovare un punto $x$ nell'intersezione di due insiemi convessi chiusi non vuoti $X$ e $Y$, tali che $X \cap Y \neq \emptyset$:
$$\text{Trovare } x \in \mathcal{H} \text{ tale che } x \in X \cap Y.$$
Questo tipo di problema è fondamentale in molte applicazioni, tra cui elaborazione di segnali e immagini, sensing compresso e elaborazione di dati sismici. Sebbene esistano metodi classici come le Proiezioni Alternate (MAP) e il metodo di Douglas-Rachford (DR), questi possono soffrire di convergenza lenta o di traiettorie a spirale (specialmente nel caso di sottospazi), che ne limitano l'efficienza pratica.

2. Metodologia: gCARPA e ns-gCARPA

Gli autori propongono un nuovo algoritmo chiamato gCARPA (Generalized Composed Alternating Relaxed Projection Algorithm), che generalizza l'algoritmo CARPA precedentemente proposto da Shen et al. [36].

• Meccanismo di Base: L'algoritmo combina dinamiche di tipo Douglas-Rachford con correzioni di tipo proiezione-riflessione.
• Rilassamenti Generalizzati: La novità principale risiede nell'introduzione di parametri di rilassamento interni $(\theta, \eta) \in (0, 1]$ per le riflessioni su entrambi gli insiemi:
  $$R^\theta_X := (1-\theta)I + \theta(2P_X - I)$$
  $$R^\eta_Y := (1-\eta)I + \eta(2P_Y - I)$$
  Dove $P_X$ e $P_Y$ sono le proiezioni ortogonali. Quando $\theta = \eta = 1$, si recuperano le riflessioni standard.
• Struttura dell'Iterazione: L'aggiornamento della sequenza $\{z_k\}$ è definito come:
  $$z_{k+1} = (1-\mu)z_k + \mu \left[ (1-\gamma)\frac{1}{2}(z_k + v_{k+1}) + \gamma y_{k+1} \right]$$
  dove $v_{k+1}$ e $y_{k+1}$ derivano dalle riflessioni rilassate e dalle proiezioni. Il parametro $\gamma$ bilancia il termine di tipo DR e il termine di proiezione, mentre $\mu$ è un parametro di rilassamento esterno.
• Variante Non Stazionaria (ns-gCARPA): Viene introdotta una versione in cui i parametri $(\gamma_k, \theta_k, \eta_k)$ variano ad ogni iterazione. I parametri sono aggiornati in modo da garantire che le variazioni siano sommabili (ad esempio, decrescendo come $O(k^{-(2+\delta)})$), permettendo all'algoritmo di adattarsi alla geometria locale del problema.

3. Contributi Chiave

1. Unificazione Teorica: gCARPA unifica diversi metodi classici (MAP, DR, RAAR, AAMR, CARPA) in un unico schema flessibile. I parametri aggiuntivi $(\theta, \eta)$ offrono gradi di libertà extra per controllare l'equilibrio tra il comportamento a spirale (tipico di DR) e l'ammortizzazione.
2. Convergenza Globale: Viene stabilita la convergenza debole (e forte in dimensione finita) della sequenza generata verso un punto nell'intersezione $X \cap Y$, sotto condizioni standard sui parametri (operatori mediati).
3. Caratterizzazione Spettrale per Sottospazi: Per il caso in cui $X$ e $Y$ sono sottospazi lineari, gli autori derivano una caratterizzazione spettrale esplicita basata sulla decomposizione degli angoli principali.
   • Viene identificato il fattore di convergenza lineare come il raggio spettrale sub-dominante di blocchi $2 \times 2$ associati agli angoli principali.
   • Viene proposta una ricetta minimax per la selezione dei parametri in un regime simmetrico, basata sulla condizione di "smorzamento critico" ($\Delta(t)=0$) agli estremi degli angoli principali (angolo di Friedrichs e angolo principale massimo).
4. Analisi della Variante Non Stazionaria: Viene dimostrata la convergenza della versione non stazionaria, trattando le variazioni dei parametri come perturbazioni sommabili di una mappa limite.

4. Risultati Sperimentali

Gli esperimenti numerici sono stati condotti su tre categorie di problemi:

• Fattibilità di Sottospazi:

  • I risultati confermano la teoria: i fattori di convergenza lineari predetti dagli autovalori corrispondono alle pendenze empiriche.
  • La scelta ottimale dei parametri $(\theta, \eta)$ tramite ricerca su griglia o la ricetta minimax permette di ottenere fattori di convergenza migliori rispetto a CARPA e DR, specialmente per angoli principali grandi.
  • La visualizzazione delle traiettorie mostra che gCARPA riduce significativamente il comportamento a spirale rispetto a DR, portando a un approccio più diretto verso l'intersezione.

• Fattibilità Non Lineare (Sfera Tangente a una Linea):

  • Questo caso è noto per essere difficile a causa dell'angolo zero all'intersezione.
  • Gli schemi stazionari mostrano una fase di coda molto lenta.
  • La variante non stazionaria (ns-gCARPA) dimostra vantaggi significativi rispetto alle versioni stazionarie e ad altri metodi (come ns-DR), riducendo il numero di iterazioni necessarie per raggiungere tolleranze elevate, grazie all'adattabilità dei parametri vicino al punto di tangenza.

• Problemi di Inverso Lineare Sparso (Sensing Compresso):

  • Su modelli realistici di recupero del segnale, gCARPA e ns-gCARPA sono competitivi o superiori rispetto a DR, MAP e GRAP.
  • In alcuni scenari specifici (es. Problema 3), gCARPA riduce il numero di iterazioni del 60-70% rispetto a CARPA, dimostrando che i parametri aggiuntivi possono adattarsi meglio alla geometria locale indotta dal modello di sensing.

5. Significato e Impatto

Questo lavoro rappresenta un avanzamento significativo nella teoria e nella pratica degli algoritmi di proiezione per problemi di fattibilità convessa:

• Flessibilità: Introduce un grado di libertà aggiuntivo (i parametri di rilassamento delle riflessioni) che permette di "sintonizzare" l'algoritmo sulla geometria specifica del problema, superando i limiti degli schemi fissi.
• Robustezza: La variante non stazionaria offre un meccanismo robusto per gestire problemi con geometrie complesse o variabili, dove una scelta fissa dei parametri non è ottimale.
• Teoria Pratica: Fornisce non solo prove di convergenza, ma anche strumenti pratici (ricetta minimax) per la selezione dei parametri nel caso di sottospazi, collegando direttamente la teoria degli angoli principali alla velocità di convergenza.

In sintesi, gCARPA offre un quadro unificato che migliora le prestazioni dei metodi esistenti, riducendo le traiettorie indesiderate e accelerando la convergenza in una vasta gamma di scenari applicativi.