A residual-iteration framework for alternating projections between affine subspaces

Resumo Técnico: Um Framework de Resíduo-Iteração para Projeções Alternadas entre Subespaços Afins

Enunciado do Problema
O artigo aborda o problema de encontrar um elemento na interseção de dois subespaços afins fechados, $U$ e $W$, dentro de um espaço de Hilbert $(H, \|\cdot\|)$. Quando a interseção é não vazia, o algoritmo clássico envolve projeções ortogonais alternadas ($u^{(n+1)} = P_U P_W u^{(n)}$). Quando a interseção é vazia (o caso inconsistente), a iteração padrão é conhecida por convergir para um ponto em $U$ mais próximo de $W$, desde que tal ponto exista. O objetivo principal deste trabalho é reformular este problema para permitir o desenvolvimento de algoritmos de projeções alternadas acelerados com garantias rigorosas de convergência tanto em cenários consistentes quanto inconsistentes.

Metodologia
A principal contribuição metodológica é a reformulação das projeções alternadas como a minimização de um funcional de mínimos quadrados associado a um operador linear limitado.

1. Reformulação de Mínimos Quadrados: O autor demonstra que a iteração de projeção alternada é equivalente a uma iteração de gradiente descendente com passo unitário para o funcional $\Phi_{U,W}(u) = \frac{1}{2}\|u - P_W u\|^2$. Ao definir um operador linear limitado $Q: U \to V^\perp$ (onde $V$ é o subespaço de direção de $W$) e um vetor $w = P_W 0$, o problema é transformado na minimização de $\Phi_{Q,w}(u) = \frac{1}{2}\|Qu - w\|^2$.
2. Framework de Iteração Resíduo-Estado: Um framework geral de "iterações resíduo-estado admissíveis" é introduzido. Este framework engloba vários algoritmos de otimização (Landweber, descida do gradiente, gradiente conjugado) ao definir iterações baseadas na evolução dos resíduos $r^{(n)} = Q^*(Qu^{(n)} - w)$ e uma variável de estado $s^{(n)}$.
3. Princípios Abstratos de Convergência: O artigo estabelece duas propriedades abstratas fundamentais para garantir a convergência forte (convergência em norma):
   • Extinção do Resíduo: A condição de que a sequência de resíduos $r^{(n)}$ converge para zero.
   • Equivariância de Translação: Uma propriedade que garante que o comportamento da iteração seja invariante sob translações específicas do iterado inicial e do vetor alvo. Isso permite que os resultados de convergência derivados para o caso de iterado inicial zero sejam transferidos para iterados iniciais arbitrários.

Principais Contribuições e Resultados

• Unificação de Métodos: O artigo prova que as projeções alternadas clássicas são exatamente a iteração de Landweber de passo unitário. Ele estende isso para incluir variantes de descida do gradiente e gradiente conjugado (CG) como acelerações naturais dentro do mesmo framework.
• Garantias de Convergência Forte:
  • Iteração de Landweber: A convergência forte é estabelecida para qualquer sequência de coeficientes de relaxação que satisfaça condições de somabilidade específicas, cobrindo tanto os casos consistentes ($M_{Q,w} \neq \emptyset$) quanto inconsistentes ($M_{Q,w} = \emptyset$). No caso inconsistente, os iterados divergem em norma, caracterizando o comportamento intrínseco quando não existe uma solução de mínimos quadrados.
  • Descida do Gradiente: O artigo fornece um resultado parcial de convergência forte, observando que a convergência total sob a única condição $M_{Q,w} \neq \emptyset$ permanece uma conjectura na literatura, embora seja provada sob condições mais fortes (por exemplo, quando o alcance de $Q$ é fechado).
  • Gradiente Conjugado: A convergência forte é estabelecida para o método CG sob a condição $M_{Q,w} \neq \emptyset$, utilizando o fato de que o CG minimiza o funcional sobre subespaços de Krylov expansíveis.
• Taxas de Convergência Linear e Taxas: Sob a suposição de que o alcance de $Q$ é fechado (equivalente ao ângulo de Friedrichs $\theta_f$ entre os subespaços ser positivo), o artigo deriva taxas de convergência linear explícitas.
  • As taxas de convergência são expressas em termos do número de condição $\kappa = \|Q\|/\gamma(Q)$, onde $\gamma(Q)$ é o módulo mínimo reduzido.
  • Geometricamente, $\|Q\|$ relaciona-se com o maior ângulo principal $\theta_p$ ($\|Q\| = \sin \theta_p$), e $\gamma(Q)$ relaciona-se com o ângulo de Friedrichs ($\gamma(Q) = \sin \theta_f$).
  • O artigo fornece limites explícitos para o decaimento do erro:
    • Landweber: $\|e^{(n)}\| \leq (1 - \epsilon/\kappa^2)^n \|e^{(0)}\|$.
    • Descida do Gradiente: $\|e^{(n)}\| \leq \kappa (1 - \frac{2}{\kappa^2+1})^n \|e^{(0)}\|$.
    • Gradiente Conjugado: $\|e^{(n)}\| \leq 2\kappa (1 - \frac{2}{\kappa+1})^n \|e^{(0)}\|$.
• Comparação de Taxas: A análise confirma a vantagem teórica do CG sobre a descida do gradiente, que por sua vez supera a iteração básica de Landweber (projeções alternadas clássicas), particularmente quando $\kappa > 1$.

Significância e Alegações
O artigo afirma fornecer um framework teórico unificado que separa a análise de algoritmos de otimização de sua interpretação geométrica como projeções. Ao estabelecer que as projeções alternadas são um caso específico de minimização de mínimos quadrados, o autor permite a transferência direta de propriedades de convergência de métodos de otimização bem estudados para algoritmos de projeção.

A significância reside em:

1. Generalização: Ir além de parâmetros de relaxação constantes para coeficientes de relaxação variáveis e diferentes estratégias de otimização (descida do gradiente, CG) mantendo provas de convergência rigorosas.
2. Tratamento da Inconsistência: Fornecer uma caracterização clara do comportamento do algoritmo quando a interseção dos subespaços é vazia, distinguindo entre convergência para uma melhor aproximação e divergência.
3. Análise Quantitativa: Oferecer taxas de convergência linear explícitas em ambientes de dimensão infinita baseadas nos ângulos geométricos entre os subespaços, um nível de detalhe que a experimentação numérica sozinha não pode capturar.
4. Insight Algébrico: O artigo destaca que restringir o iterado inicial ao subespaço $U$ permite uma formulação autoadjunta ($L_\alpha$) que simplifica a análise das taxas de convergência em comparação com o caso geral envolvendo operadores não autoadjuntos ($F_\alpha$).

O trabalho conclui que esta perspectiva baseada em otimização oferece uma metodologia geral para construir e analisar métodos de projeção alternada, sugerindo aplicações futuras para outras técnicas de otimização, como métodos quasi-Newton e estratégias de regularização.