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

Resumen Técnico: Algoritmo de Proyección Relajada Alternada Compuesta Generalizado para el Problema de Factibilidad de Dos Conjuntos

1. El Problema

El artículo aborda el problema de factibilidad de dos conjuntos, que consiste en encontrar un punto $x$ en la intersección de dos conjuntos convexos cerrados no vacíos $X$ e $Y$ en un espacio de Hilbert real $H$:
$$\text{encontrar } x \in X \cap Y$$
Este problema es fundamental en diversas aplicaciones como procesamiento de señales e imágenes, sensores comprimidos (compressed sensing) y procesamiento de datos sísmicos. Los métodos basados en proyecciones son populares por su simplicidad y teoría de convergencia robusta. Sin embargo, métodos clásicos como la Proyección Alternada (MAP) pueden converger lentamente, y métodos tipo Douglas-Rachford (DR) pueden exhibir trayectorias de "espiral" pronunciadas que ralentizan el progreso práctico, especialmente en problemas de subespacios.

2. Metodología: gCARPA y ns-gCARPA

Los autores proponen un nuevo algoritmo llamado gCARPA (Generalized Composed Alternating Relaxed Projection Algorithm) y su variante no estacionaria ns-gCARPA.

• Mecanismo Central: El algoritmo combina dinámicas de tipo Douglas-Rachford con correcciones de tipo proyección-reflexión. Introduce relajaciones internas mediante parámetros $(\theta, \eta)$ en las reflexiones de los conjuntos $X$ e $Y$, y un paso de promediado externo con parámetro $\mu$.
  • Las reflexiones relajadas se definen como:
    $$R^\theta_X = (1-\theta)I + \theta(2P_X - I)$$
    $$R^\eta_Y = (1-\eta)I + \eta(2P_Y - I)$$
    Donde $P_X$ y $P_Y$ son proyecciones ortogonales. Cuando $\theta=\eta=1$, se recuperan las reflexiones estándar.
• Actualización del Algoritmo: La iteración se formula como un punto fijo relajado:
  $$z_{k+1} = (1-\mu)z_k + \mu F^\theta_{\gamma}(z_k)$$
  Donde el operador $F$ es una combinación convexa de un término tipo DR y un término de proyección.
• Variante No Estacionaria (ns-gCARPA): Permite que los parámetros $(\gamma_k, \theta_k, \eta_k)$ varíen a lo largo de las iteraciones bajo condiciones de suma de errores (incrementos sumables), adaptándose a la geometría local del problema.

3. Contribuciones Clave

1. Unificación y Generalización: gCARPA unifica varios métodos clásicos (MAP, DR, RAAR, AAMR, GRAP) y extiende el algoritmo CARPA previo [36] al introducir los parámetros de relajación $(\theta, \eta)$. Esto ofrece grados de libertad adicionales para controlar el equilibrio entre el comportamiento de "espiral" y el amortiguamiento.
2. Análisis de Convergencia Global: Se establece la convergencia global débil para conjuntos convexos cerrados bajo elecciones adecuadas de parámetros. En espacios de dimensión finita, la convergencia es fuerte.
3. Caracterización Espectral para Subespacios: Para el caso donde $X$ y $Y$ son subespacios lineales, los autores derivan una caracterización espectral explícita utilizando descomposiciones de ángulos principales.
   • Se identifican factores de eigenvalores subdominantes computables.
   • Se propone una receta de selección de parámetros minimax en un régimen simétrico que busca el amortiguamiento crítico en los planos de ángulos principales, optimizando la tasa de convergencia lineal.
4. Convergencia de la Variante No Estacionaria: Se demuestra la convergencia del esquema no estacionario bajo la suposición de que los parámetros convergen a un límite y sus variaciones son sumables.

4. Resultados Experimentales

Los autores realizaron experimentos numéricos en tres escenarios principales:

• Factibilidad de Subespacios:
  • Se verificó que las tasas de convergencia lineal empíricas coinciden con las predicciones teóricas basadas en los ángulos de Friedrichs.
  • gCARPA, con una selección adecuada de $(\theta, \eta)$, logra factores de convergencia superiores a los de CARPA y DR, especialmente en ángulos grandes.
  • La visualización de trayectorias muestra que los parámetros relajados reducen significativamente el comportamiento de espiral rotacional típico de DR.
• Intersección de una Bola Tangente a una Línea (No Convexa/No Suave):
  • Este caso es difícil debido al ángulo cero en el punto de intersección.
  • Los métodos estacionarios sufren de una fase de cola lenta.
  • La variante ns-gCARPA demostró ser superior en regímenes de alta precisión, adaptando los parámetros para mitigar la ralentización cerca del punto de tangencia, superando a ns-DR y ns-CARPA en tolerancias estrictas.
• Problemas Inversos Lineales Escasos (Compressed Sensing):
  • Se probaron en modelos realistas con matrices de diccionarios (DCT, Dirac, Gaussiano).
  • gCARPA y ns-gCARPA mostraron ser competitivos o superiores a los métodos base (DR, MAP, GRAP, CARPA) en varios casos, reduciendo el número de iteraciones necesarias para alcanzar la precisión.
  • En algunos casos, la adaptación no estacionaria mejoró la robustez, aunque en otros la variación agresiva de parámetros introdujo efectos transitorios.

5. Significado e Impacto

Este trabajo es significativo porque:

• Mejora Práctica: Proporciona un marco flexible que puede superar a los métodos de proyección/reflexión estándar en problemas dependientes de la geometría, ofreciendo una herramienta para "afinar" la dinámica del algoritmo.
• Fundamento Teórico: Ofrece una comprensión profunda de cómo los parámetros de relajación afectan la convergencia lineal en subespacios, proporcionando reglas prácticas (recetas minimax) para seleccionar parámetros óptimos sin necesidad de búsqueda exhaustiva.
• Versatilidad: Demuestra que la combinación de relajación interna y esquemas no estacionarios puede abordar tanto problemas lineales (subespacios) como no lineales o mal condicionados (tangencia, sensores comprimidos), manteniendo la simplicidad computacional de las proyecciones.

En resumen, el artículo presenta una generalización potente de los métodos de proyección alternada que, mediante el control fino de la relajación y la adaptación dinámica, logra acelerar la convergencia y mejorar la robustez en una amplia gama de problemas de factibilidad convexa.