Convergence rates for pivoted QR and LU

Resumo Técnico: Taxas de Convergência para QR e LU com Pivoteamento

Enunciado do Problema
As decomposições QR com pivoteamento e LU com pivoteamento são amplamente utilizadas como algoritmos gulosos (greedy) para o cálculo de aproximações de baixo posto de matrizes e funções. Embora esses métodos demonstrem um forte desempenho prático, sua justificativa teórica historicamente baseou-se em limites de pior caso que contêm fatores de crescimento exponencial (ex: $4^k$ ou $2^k$). Esses limites sugerem que a convergência só é garantida quando os valores singulares decrescem geometricamente a uma taxa suficiente para superar os fatores exponenciais (ex: $\rho < 1/4$). No entanto, na prática, esses algoritmos frequentemente convergem de forma eficaz mesmo sob um decaimento de valores singulares mais modesto (decaimento algébrico ou geométrico mais lento). O artigo aborda a lacuna entre esses limites pessimistas de pior caso e o comportamento prático observado, derivando taxas de convergência que dependem diretamente do decaimento dos valores singulares ou da regularidade da função, sem fatores de penalidade exponenciais.

Metodologia
O núcleo da análise baseia-se em dois componentes primários:

1. Pivoteamento Guloso Aproximado: Os autores relaxam o requisito de pivoteamento guloso exato (seleção da entrada absoluta máxima ou da norma da coluna) para o pivoteamento guloso aproximado. Neste esquema, o pivô selecionado $p_{k+1}$ satisfaz $|p_{k+1}| \ge \gamma \|E^{(k)}\|_{\max}$ (para LU) ou $\rho_{k+1} \ge \gamma \|E^{(k)}\|_{2,\infty}$ (para QR), onde $0 < \gamma \le 1$ é uma constante de qualidade.
2. Identidades de Produto de Pivôs e Limites de Determinante: A análise utiliza identidades clássicas que ligam o produto dos pivôs ao determinante de uma submatriz formada pelos índices selecionados.
   • Para LU, $\det(A_{I_n, J_n}) = \prod_{j=1}^n p_j$.
   • Para QR, $(\det(G_n))^{1/2} = \prod_{j=1}^n \rho_j$, onde $G_n$ é a matriz de Gram das colunas selecionadas.

Ao combinar essas identidades com a condição de pivoteamento aproximado, os autores limitam o resíduo mínimo sobre as primeiras $n$ iterações pela média geométrica dos primeiros $n$ valores singulares (para matrizes) ou por limites no determinante de submatrizes amostradas (para funções).

Principais Contribuições e Resultados

1. Caso Matricial (QR e LU com Pivoteamento)
O artigo estabelece que o erro desses algoritmos é controlado pela média geométrica dos principais valores singulares, $\left(\prod_{j=1}^n \sigma_j(A)\right)^{1/n}$.

• Decaimento Algébrico: Se os valores singulares decrescem algebricamente como $\sigma_k(A) = O(k^{-p})$, os resíduos para ambos, LU e QR, convergem na mesma taxa algébrica $O(k^{-p})$. Isso contrasta com limites anteriores que exigiam decaimento exponencial para garantir a convergência.
• Decaimento Geométrico: Se os valores singulares decrescem geometricamente como $\sigma_k(A) = O(\rho^k)$, os resíduos convergem na taxa geométrica $O(\rho^{k/2})$.
• Robustez: Estes resultados sustentam-se sob pivoteamento guloso aproximado, com o limite de erro escalonado apenas por uma constante multiplicativa $\gamma^{-1}$.

2. Caso Funcional (LU com Pivoteamento para Funções)
A análise é estendida para aproximar funções bivariadas $f(x, y)$ via expansões separáveis. O algoritmo seleciona pontos de pivô $(x_k, y_k)$ para minimizar o resíduo na norma $L^\infty$.

• Taxas Baseadas em Regularidade: As taxas de convergência são derivadas limitando os determinantes de submatrizes amostradas $[f(x_i, y_j)]$ com base na suavidade de $f$.
  • Funções de Hölder/Diferenciáveis: Para funções com $q_x$ derivadas em $x$ e $q_y$ em $y$ (com continuidade de Hölder $\alpha_x, \alpha_y$), o artigo deriva taxas de convergência algébricas. Especificamente, se $f$ é meramente $\alpha_x$-Hölder em uma variável com $\alpha_x > 1/2$, a convergência é garantida. A regularidade mista produz taxas aprimoradas (ex: $O(n^{-(2q-1/2)})$ para funções $q$-vezes diferenciáveis com derivadas mistas).
  • Funções Analíticas: Para funções analíticas em elipses de Bernstein com parâmetros $\rho_x, \rho_y > 1$, o artigo estabelece convergência geométrica. Sob analiticidade unilateral, a taxa é $O(\rho^{-n/2})$; sob analiticidade conjunta, melhora para $O((\rho_x \rho_y)^{-n/2})$. Estes resultados sustentam-se para qualquer $\rho > 1$, melhorando os requisitos anteriores de $\rho > 4$.

Significância e Alegações
O artigo afirma fornecer uma explicação teórica para o desempenho robusto dos algoritmos QR e LU com pivoteamento em regimes onde os limites tradicionais de pior caso são informativos.

• Novos Limites Teóricos: Os autores afirmam que as taxas de convergência de LU sob decaimento de valor singular são novas. Para QR, embora existam taxas semelhantes na literatura de bases reduzidas (via larguras de Kolmogorov), este trabalho fornece estimativas com constantes explícitas menores e dependência linear na qualidade do pivô $\gamma^{-1}$, em vez de quadrática.
• Aproximação Funcional: O artigo apresenta os primeiros resultados gerais de taxa de convergência para LU com pivoteamento aplicado a funções que não requerem suposições de analiticidade ou definição positiva.
• Robustez Algorítmica: Uma descoberta significativa é que a análise acomoda perfeitamente o pivoteamento guloso aproximado. Isso sugere que estratégias heurísticas de seleção de pivô (comuns na prática para reduzir o custo computacional) mantêm as mesmas taxas de convergência que o pivoteamento exato, até um fator constante.

Os autores concluem que o custo dominante nesses algoritmos é frequentemente a busca pelo pivô, e seus resultados apoiam o uso de estratégias de pivoteamento aproximado sem sacrificar as taxas de convergência. Nota-se que trabalhos futuros podem estender essas estimativas baseadas em suavidade para dimensões mais altas e classes de funções mais amplas.