A Sketched Generalized Krylov Subspace Method for Large-Scale Regularization

Resumo Técnico: Um Método de Subespaço de Krylov Generalizado Esboçado para Regularização em Larga Escala

Definição do Problema
O artigo aborda problemas de mínimos quadrados de larga escala e mal condicionados da forma $\min_{x} \|Ax - b\|_2^2$, onde a matriz $A$ é severamente mal condicionada e $b$ contém ruído. Para estabilizar a solução, utiliza-se a regularização de Tikhonov, levando ao problema penalizado:
$$\min_{x \in \mathbb{R}^n} \left\{ \|Ax - b\|_2^2 + \lambda \|Lx\|_2^2 \right\},$$
onde $L$ é uma matriz de regularização geral que codifica informações prévias. Embora existam métodos eficientes para a Tikhonov de forma padrão ($L=I$), lidar com um $L$ geral é computacionalmente desafiador. O método de Subespaço de Krylov Generalizado (GKS) [28] foi proposto para lidar com o $L$ geral expandindo um espaço de busca usando o gradiente do funcional de Tikhonov. No entanto, à medida que a dimensão do subespaço cresce, o GKS enfrenta dois gargalos computacionais proibitivos:

1. Fatorações QR Magras: Atualizar as fatorações QR das matrizes projetadas $AV_k$ e $LV_k$ a cada iteração.
2. Reortogonalização: Reortogonalizar explicitamente os novos vetores da base contra todas as colunas anteriores para manter a estabilidade numérica, o que exige computações completas de produto interno.

Essas operações escalam desfavoravelmente com o número de iterações e o tamanho do problema, limitando a escalabilidade do GKS para problemas inversos de larga escala.

Metodologia: sGKS (Sketched GKS)
Os autores propõem o sGKS, uma variante randomized do método GKS que utiliza sketching (redução de dimensionalidade aleatória) para acelerar as etapas mais caras enquanto preserva a qualidade da aproximação. A metodologia baseia-se em duas observações primárias:

1. Eliminação da Reortogonalização Explícita: Os autores observam que o algoritmo GKS não depende intrinsecamente da ortogonalidade dos vetores da base para seus passos principais (ao contrário dos métodos de Krylov clássicos para sistemas lineares que dependem de relações Arnoldi/Lanczos). Consequentemente, o sGKS ignora a reortogonalização explícita da base por completo. Em vez de manter uma base ortonormal $V_k$, o sGKS mantém uma base não ortonormal $W_k$ formada pela concatenação dos vetores de gradiente brutos. Isso remove o custo de $O(d_k^2 n)$ da reortogonalização (onde $d_k$ é a dimensão do subespaço).

2. Sketch-and-Solve para Problemas Projetados: Para reduzir o custo de resolver o problema de Tikhonov projetado e atualizar as fatorações QR, o sGKS emprega operadores de sketching $S_A$ e $S_L$.

   • O problema de mínimos quadrados projetado é resolvido em matrizes comprimidas $S_A A W_k$ e $S_L L W_k$ em vez de $A W_k$ e $L W_k$ completos.
   • As fatorações QR são realizadas nessas matrizes esboçadas de tamanho $s \times d_k$ (onde $s \ll m, p$) e atualizadas incrementalmente via extensões de posto um (rank-one extensions).
   • Os operadores de sketching utilizados são Oblivious Subspace Embeddings (especificamente Subsampled Randomized Trigonometric Transforms, SRTT), que dependem apenas da dimensão do subespaço, não do subespaço em si.

Principais Contribuições

• Design Algorítmico: O desenvolvimento do sGKS, que integra o sketching aleatório na estrutura GKS para regularização de Tikhonov de forma geral.
• Análise Teórica:
  • Equivalência: Os autores provam que, se o sketching for omitido na resolução projetada, o sGKS produz iterações matematicamente idênticas ao GKS padrão (Proposição 1).
  • Quase-Otimalidade: Eles demonstram que, quando o sketching é aplicado, o método produz normas de resíduo quase ótimas, com o erro controlado pela qualidade de incorporação ($\epsilon$) dos operadores de sketching (Proposição 2).
  • Refinamento Iterativo: Para casos em que a perda de ortogonalidade da base se torna significativa (levando à deficiência de posto numérico), o artigo mostra que incorporar um pequeno número de passos de refinamento iterativo (IR) na resolução projetada restaura as propriedades espectrais da base e recupera a precisão total do método sem sketching.
• Eficiência Computacional: O método reduz os custos por iteração substituindo atualizações QR de posto total e reortogonalização caras por operações mais baratas em matrizes comprimidas.

Resultados Numéricos
O artigo avalia o sGKS em quatro problemas inversos de larga escala:

1. Deblurring de Imagem: O sGKS com várias dimensões de sketch ($s$) alcança uma qualidade de reconstrução comparável ao GKS padrão. Um $s$ maior produz trajetórias de convergência quase indistinguíveis do GKS, enquanto um $s$ menor resulta em erros finais ligeiramente maiores, mas com convergência mais rápida.
2. Reconstrução de Tomografia Computadorizada de Raios-X: Em um problema com $n=250.000$ incógnitas e um operador de regularização grande ($p \approx 500.000$), o sGKS iguala a precisão de reconstrução do GKS (RRE $\approx 0,183$) enquanto reduz significativamente o tempo de execução (wall-clock time). A aceleração é impulsionada pela eliminação da reortogonalização e pela redução dos custos de atualização QR de $O(p)$ para $O(s)$.
3. Tomografia de Tempo de Viagem Sísmica: Em um sistema esparso e sobredeterminado, o sGKS supera os métodos híbridos LSQR tanto em precisão quanto em velocidade. Embora a aceleração sobre o GKS padrão seja modesta aqui (já que o cálculo do gradiente é dominante), o sGKS ainda proporciona uma redução de 10% no tempo, mantendo uma qualidade de reconstrução superior em comparação com variantes do LSQR.
4. CT Dinâmica: Em uma formulação espaço-temporal com um operador de regularização massivo, os custos de QR e reortogonalização dominam o tempo de execução do GKS padrão. Aqui, o sGKS alcança uma aceleração de 3$\times$ sobre o GKS padrão. A inclusão de refinamento iterativo (IR) permite que o sGKS recupere a trajetória de convergência exata e o parâmetro de regularização ótimo do GKS sem sketching, enquanto o sGKS sem IR estagna em um erro ligeiramente superior.

Significância e Alegações
O artigo afirma que o sGKS é uma alternativa escalável ao GKS padrão para regularização de larga escala com matrizes gerais. Sua significância reside em:

• Escalabilidade: Ele remove os gargalos computacionais (reortogonalização e atualizações QR de posto total) que anteriormente limitavam a aplicabilidade do GKS a problemas muito grandes.
• Preservação de Precisão: Mantém a qualidade de reconstrução do método original, com garantias teóricas sobre normas de resíduo e evidência empírica de que o refinamento iterativo pode recuperar a precisão total mesmo quando a ortogonalidade da base é perdida.
• Generalidade: A abordagem é independente da escolha específica do operador de sketching e aplica-se a matrizes de regularização gerais, não apenas a problemas de forma padrão.

Os autores concluem que, embora o método introduza um parâmetro de sketching ($s$) para ajustar o equilíbrio entre velocidade e precisão, ele oferece um arcabouço robusto para resolver problemas inversos de larga escala onde os métodos de projeção padrão são computacionalmente proibitivos. O trabalho futuro sugerido inclui a seleção adaptativa da dimensão de sketch e extensões para problemas inversos não lineares.