A Variational Equation and Lower Bound for the Linear Least-Squares Backward Error

Resumo Técnico: Uma Equação Variacional e Limite Inferior para o Erro Atrás Linear de Mínimos Quadrados

Enunciado do Problema
O artigo aborda o desafio de estimar eficientemente o erro atrás, $\mu$, para problemas de mínimos quadrados lineares com múltiplos lados direitos:
$$\min_{X \in \mathbb{R}^{n \times d}} \|AX - B\|_F$$
onde $A \in \mathbb{R}^{m \times n}$ e $B \in \mathbb{R}^{m \times d}$. O erro atrás $\mu$ é definido como a norma mínima de perturbações $[E, \theta F]$ tais que a solução aproximada $X$ se torne uma solução exata para o sistema perturbado $(A+E)^T(A+E)X = (A+E)^T(B+F)$.

O cálculo direto de $\mu$ é proibitivamente caro para solvers iterativos, pois requer a resolução de um grande problema de autovalores ou de um problema generalizado de autovalores. Embora existam estimativas (como a estimativa de Karlson-Waldén), elas são frequentemente caras de calcular exatamente ou carecem de limites garantidos (ou seja, não são estritamente limites superiores ou inferiores). O artigo busca um método para derivar estimativas confiáveis e computacionalmente baratas, focando especificamente em limites inferiores que possam servir como critérios de parada para métodos iterativos como LSQR e LSMR.

Metodologia
A metodologia central baseia-se em expressar o erro atrás em termos de um problema generalizado de autovalores no âmbito da álgebra linear indefinida.

1. Formulação Variacional: O artigo estabelece primeiro uma equação variacional para o erro atrás $\mu(A, R_\theta)$, onde $R_\theta$ é uma matriz residual transformada. Ele expressa $\mu$ como um problema de maximização sobre uma variedade indefinida definida pela restrição $X^T J_{n,d} X = -I_d$, onde $J_{n,d} = \text{diag}(I_n, -I_d)$.
   $$\mu(A, R_\theta) = \sup_{X^T J_{n,d} X = -I_d} \left( \|R_\theta\|_F^2 - \|[A, R_\theta]X\|_F^2 \right)^{1/2}$$
2. Decomposição CS Hiperbólica: Para resolver este problema de otimização, os autores utilizam a decomposição CS hiperbólica (um análogo indefinido da decomposição CS para matrizes unitárias). Esta decomposição permite que a otimização sobre a matriz $X$ seja desacoplada em otimizações sobre matrizes ortogonais e matrizes de escala diagonal.
3. Teorema de Decomposição: Ao aplicar esta decomposição, o artigo deriva um teorema mostrando que o erro atrás para um problema com $d$ lados direitos pode ser decomposto na soma de $d$ problemas de erro atrás menores, cada um envolvendo um único lado direito.
4. Construção do Limite Inferior: Aproveitando esta decomposição, os autores propõem um limite inferior baseado em sketching. Ao calcular um único vetor de teste $p$ usando uma matriz sketch $SA$ (onde $S$ é uma matriz de sketching), eles podem avaliar a fórmula de erro atrás de lado direito único. Isso fornece um limite inferior provável sobre o verdadeiro erro atrás.

Principais Contribuições

• Teorema 1 (Decomposição): A contribuição teórica primária é a decomposição do erro atrás $\mu(A, R_\theta)$ em uma soma de termos menores:
  $$\mu(A, R_\theta) = \max_{P, Q} \left( \sum_{i=1}^k \mu^2(Ap_i, R_\theta q_i) \right)^{1/2}$$
  onde $P$ e $Q$ são matrizes com colunas ortonormais. Isso reduz a complexidade do problema a uma série de otimizações escalares.
• Expressão Exata para Lado Direito Único: O artigo fornece uma expressão estável e de forma fechada para o erro atrás no caso de lado direito único, $\mu(a, r)$, que depende das normas da soma e da diferença dos vetores:
  $$\mu(a, r) = \frac{2|a^T r|}{\|a+r\|_2 + \|a-r\|_2}$$
• Limite Inferior Baseado em Sketching: Os autores propõem um novo limite inferior para métodos iterativos. Ao usar uma matriz de sketch $S$ para calcular uma direção aproximada $p$, eles podem avaliar a fórmula de lado direito único para obter um valor $\mu(Ap/\|p\|_2, r_\theta)$.
  • Este valor é provavelmente um limite inferior sobre o verdadeiro erro atrás.
  • O artigo prova que este limite inferior é de qualidade comparável à estimativa de Karlson-Waldén sketch, satisfazendo especificamente a desigualdade:
    $$\frac{1-\eta^2}{1+\eta^2} \nu(A, r_\theta) \leq \mu(Ap/\|p\|_2, r_\theta) \leq \mu(A, r_\theta)$$
    onde $\eta$ representa a distorção do sketch e $\nu$ é a estimativa de Karlson-Waldén.
• Refinamento Iterativo e Reciclagem: O artigo discute métodos para melhorar esta estimativa através do refinamento iterativo do vetor $p$ e da "reciclagem" do vetor computado $Ap$ ao longo das iterações para reduzir o custo computacional.

Resultados
Experimentos numéricos foram conduzidos usando o solver LSMR em uma matriz da coleção SuiteSparse com um número de condição alto ($\approx 3.5 \times 10^{16}$). Os resultados indicam:

• O limite inferior proposto é consistentemente comparável em precisão à estimativa de Karlson-Waldén sketch.
• Em casos com sketches mais baratos ($n_{sketch}$ menor), o limite inferior proposto foi às vezes mais preciso que a estimativa de Karlson-Waldén sketch.
• O limite inferior "reciclado" (reutilizando $Ap$ ao longo das iterações) permaneceu próximo do verdadeiro erro atrás por uma parte significativa do histórico de iterações, sugerindo utilidade como um monitor de erro barato.
• O refinamento iterativo do vetor $p$ melhorou a precisão apenas quando o tamanho do sketch era muito grande ($16n$), sugerindo que, para tamanhos de sketch padrão, o custo computacional adicional pode não ser justificado.
• Tentativas de construir limites superiores usando técnicas semelhantes foram encontradas como apenas marginalmente melhores que limites simples existentes (como $\|A^T r\|_2 / \|r\|_2$) e ainda superestimaram significativamente o erro verdadeiro.

Significado e Alegações
O artigo afirma que seu significado primário é teórico: ele fornece uma decomposição do erro atrás que leva naturalmente a limites inferiores computáveis.

• Confiabilidade: Ao contrário da estimativa de Karlson-Waldén sketch, que não é garantida ser um limite superior ou inferior, o método proposto produz um limite inferior estrito. Isso é valioso para critérios de parada, pois garante que o erro verdadeiro é pelo menos tão grande quanto a estimativa.
• Eficiência: O método permite a conversão de uma estimativa baseada em sketch em um limite inferior com qualidade comparável, mas com a garantia adicional de ser um limite.
• Modéstia: Os autores são modestos quanto aos limites superiores, notando que suas tentativas de produzir limites superiores de maneira similar foram "geralmente malsucedidas". Eles reconhecem que a decomposição para múltiplos lados direitos envolve a otimização sobre duas matrizes ($P$ e $Q$), o que é mais complexo que a otimização de um único vetor requerida para o limite inferior. Trabalho futuro é sugerido para abordar o caso de múltiplos lados direitos e investigar por que encontrar bons limites superiores parece mais difícil do que encontrar bons limites inferiores.