A fast solver for ill-conditioned linear systems using randomized stable solutions of its blocks

Enunciado do Problema
O artigo aborda o desafio de resolver sistemas lineares consistentes de equações $Ax = b$, onde $A \in \mathbb{R}^{m \times n}$ e $b \in \mathbb{R}^{m \times 1}$. O foco principal recai sobre sistemas altamente mal condicionais, incluindo sistemas esparsos, problemas de mínimos quadrados densos e casos que são significativamente sobredeterminados ou subdeterminados. Os autores destacam que os métodos iterativos padrão, como o GMRES, frequentemente enfrentam dificuldades com esses sistemas porque a minimização da norma do resíduo não garante necessariamente a convergência no erro relativo para problemas mal condicionados. Além disso, as técnicas de pré-condicionamento tradicionais (ex: ILU, Jacobi) podem sofrer de instabilidade numérica, quebra de pivô ou preenchimento excessivo (fill-in) quando aplicadas a matrizes com números de condição muito elevados, falhando precisamente quando a aceleração robusta é mais necessária.

Metodologia
Os autores propõem um algoritmo aprimorado denominado Regularized Orthogonality and Residual based Block-Kaczmarz (ROR-BK). Este método baseia-se na estrutura de Kaczmarz em blocos randomizados, mas introduz três melhorias específicas para aumentar a estabilidade e a convergência:

1. Agregação Dinâmica Baseada no Resíduo: Em vez de depender apenas de blocos fixos, o método agrega dinamicamente um subconjunto de equações em cada iteração com base no vetor de resíduo atual. Especificamente, ele seleciona as linhas que mais contribuem para o resíduo quadrático para formar um bloco, visando minimizar a norma do resíduo de forma mais eficaz em cada etapa.
2. Amostragem de Ortogonalidade Mútua Eficaz: O método generaliza o conceito de ortogonalidade entre pares de blocos (usado no Simple Orthogonal Block-Kaczmarz ou SOBK) para a "ortogonalidade efetiva" de um único bloco contra todos os outros blocos. Uma matriz simétrica $C$ é computada, onde as entradas representam o cosseno do ângulo efetivo entre os centroides dos blocos. Os blocos são então amostrados probabilisticamente com base em uma distribuição que favorece blocos com alta ortogonalidade cumulativa em relação ao restante do sistema.
3. Regularização: Para garantir a estabilidade numérica, particularmente quando os blocos são deficientes em posto (rank-deficient) ou mal condicionados, as atualizações de bloco utilizam uma pseudo-inversa regularizada. Em vez da inversa de Moore-Penrose padrão $B^\dagger = B^T(BB^T)^{-1}$, o método utiliza a forma regularizada $B^T(BB^T + \mu I)^{-1}$, onde $\mu$ é uma constante positiva pequena. Isso é interpretado como um algoritmo de ponto proximal estocástico.

O algoritmo opera alternando entre atualizações usando os blocos amostrados por ortogonalidade e atualizações usando os blocos dinâmicos baseados no resíduo. Os autores também demonstram que este método pode servir como uma iteração interna (pré-condicionador) para solucionadores GMRES flexíveis (FAB-GMRES).

Principais Contribuições

• Inovação Algorítmica: A introdução do ROR-BK, que combina seleção dinâmica de blocos baseada no resíduo, amostragem de ortogonalidade global consciente e regularização do tipo Tikhonov dentro de uma estrutura de Block-Kaczmarz.
• Análise Teórica: O artigo fornece uma análise de convergência (Teoremas 2.3 e 2.4) mostrando que o método alcança convergência estável mesmo quando os blocos são numericamente deficientes em posto. Estabelece-se que a redução do erro é limitada pelo parâmetro de regularização $\mu$ e pelo menor autovalor não nulo das matrizes de bloco. O Teorema 2.4 argumenta ainda que a seleção de blocos baseada no resíduo máximo melhora os limites superior e inferior do erro.
• Estratégia de Pré-condicionamento: A proposta de usar o ROR-BK como um pré-solucionador ou iteração interna para acelerar a solução de sistemas mal condicionados sem a necessidade de pré-condicionadores externos explícitos e potencialmente instáveis.

Resultos
Os autores conduziram extensos experimentos numéricos comparando o ROR-BK contra:

• Solucionadores Randomizados: Simple Orthogonal Block-Kaczmarz (SOBK) e Tail Averaged Regularized Block Kaczark (TA-ReBlocK-U).
• Solucionadores de Subespaço de Krylov: LSQR e várias variantes de GMRES (AB/BA-GMRES) com pré-condicionadores como Jacobi, ILU e Robust Incomplete Factorization (RIF).

Descobertas de Desempenho:

• Velocidade e Iterações: Em uma ampla gama de matrizes de teste (incluindo matrizes esparsas da coleção da Universidade da Flórida e matrizes densas geradas aleatoriamente), o ROR-BK consistentemente exigiu menos iterações e menos tempo de CPU do que o SOBK e o TA-ReBlocK-U. As acelerações variaram de 1,23x a 5,17x sobre o SOBK e até 49,08x sobre o TA-ReBlocK-U em termos de tempo de CPU.
• Sistemas Mal Condicionados: Em cenários altamente mal condicionados (números de condição até $10^{20}$), muitos solucionadores de Krylov e suas versões pré-condicionadas falharam em convergir dentro do limite de iterações ou produziram grandes erros relativos. O ROR-BK convergiu com sucesso nesses casos, frequentemente alcançando erros relativos menores.
• Aplicação no Mundo Real: O método foi testado em problemas de reconstrução de imagem (tomografia de feixe paralelo e RM) envolvendo dados ruidosos e sistemas severamente subdeterminados. O ROR-BK demonstrou desempenho superior em termos de Relação Sinal-Ruído de Pico (PSNR) e Índice de Similaridade Estrutural (SSIM) comparado a outros métodos, particularmente em cenários onde outros solucionadores sofreram com instabilidade ou falha.

Significância e Alegações
O artigo afirma que o ROR-BK oferece uma alternativa promissora para resolver sistemas lineares onde a matriz $A$ é mal condicionada, alcançando aproximações eficientes sem a necessidade de pré-condicionamento explícito. Os autores argumentam que, embora os pré-condicionadores visem reduzir o número de condição da matriz, eles não reduzem necessariamente o número de condição do problema em si e podem introduzir instabilidade numérica. Ao particionar o sistema em blocos e utilizar ortogonalidade efetiva e regularização, o ROR-BK distribui as equações covariantes em subproblemas potencialmente bem condicionados.

Os autores posicionam o método como um solucionador robusto para sistemas quadrados, sob determinados e sob determinados. Eles sugerem ainda sua utilidade como um pré-solucionador ou iteração interna para acelerar outros métodos iterativos como o GMRES, particularmente em casos onde as técnicas de pré-condicionamento padrão falham devido a quebras de pivô ou deficiência de posto. O trabalho enfatiza que a combinação de dinâmica baseada no resíduo e amostragem de ortogonalidade fornece um mecanismo simples, porém eficaz, para convergência rápida e estável em sistemas lineares de alto número de condição.