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

Planteamiento del Problema
El artículo aborda el desafío de resolver sistemas lineales consistentes de ecuaciones $Ax = b$, donde $A \in \mathbb{R}^{m \times n}$ y $b \in \mathbb{R}^{m \times 1}$. El enfoque principal se centra en sistemas altamente mal condicionados, incluyendo sistemas dispersos (sparse), problemas de mínimos cuadrados densos y casos que son significativamente sobredeterminados o subdeterminados. Los autores destacan que los métodos iterativos estándar, como GMRES, a menudo tienen dificultades con estos sistemas porque la minimización de la norma del residuo no garantiza necesariamente la convergencia en el error relativo para problemas mal condicionados. Además, las técnicas de precondicionamiento tradicionales (por ejemplo, ILU, Jacobi) pueden sufrir de inestabilidad numérica, rupturas de pivote o un exceso de llenado (fill-in) cuando se aplican a matrices con números de condición muy grandes, fallando precisamente cuando se necesita una aceleración robusta.

Metodología
Los autores proponen un algoritmo mejorado denominado Regularized Orthogonality and Residual based Block-Kaczmarz (ROR-BK). Este método se basa en el marco de trabajo de Kaczmarz de bloques aleatorios e introduce tres mejoras específicas para mejorar la estabilidad y la convergencia:

1. Agregación Dinámica Basada en el Residuo: En lugar de depender únicamente de bloques fijos, el método agrega dinámicamente un subconjunto de ecuaciones en cada iteración basándose en el vector de residuo actual. Específicamente, selecciona las filas que más contribuyen al residuo al cuadrado para formar un bloque, con el objetivo de minimizar la norma del residuo de manera más efectiva en cada paso.
2. Muestreo de Ortogonalidad Efectiva Mutua: El método generaliza el concepto de ortogonalidad entre pares de bloques (utilizado en el Simple Orthogonal Block-Kaczmarz o SOBK) a la "ortogonalidad efectiva" de un solo bloque contra todos los demás bloques. Se calcula una matriz simétrica $C$ donde las entradas representan el coseno del ángulo efectivo entre los centroides de los bloques. Luego, los bloques se muestrean probabilísticamente basándose en una distribución que favorece a los bloques con alta ortogonalidad acumulada respecto al resto del sistema.
3. Regularización: Para garantizar la estabilidad numérica, particularmente cuando los bloques son deficientes en rango o están mal condicionados, las actualizaciones de bloque utilizan una pseudo-inversa regularizada. En lugar de la inversa de Moore-Penrose estándar $B^\dagger = B^T(BB^T)^{-1}$, el método utiliza la forma regularizada $B^T(BB^T + \mu I)^{-1}$, donde $\mu$ es una constante positiva pequeña. Esto se interpreta como un algoritmo de punto proximal estocástico.

El algoritmo opera alternando entre actualizaciones utilizando los bloques muestreados por ortogonalidad y actualizaciones utilizando los bloques dinámicos basados en el residuo. Los autores también demuestran que este método puede servir como una iteración interna (precondicionador) para solucionadores de GMRES flexibles (FAB-GMRES).

Contribuciones Clave

• Innovación Algorítmica: La introducción de ROR-BK, que combina la selección dinámica de bloques basada en el residuo, el muestreo consciente de la ortogonalidad global y la regularización de tipo Tikhonov dentro de un marco de trabajo de Block-Kaczmarz.
• Análisis Teórico: El artículo proporciona un análisis de convergencia (Teoremas 2.3 y 2.4) que muestra que el método logra una convergencia estable incluso cuando los bloques son numéricamente deficientes en rango. Establece que la reducción del error está acotada por el parámetro de regularización $\mu$ y el menor autovalor no nulo de las matrices de bloque. El Teorema 2.4 argumenta además que la selección de bloques basada en los residuos máximos mejora los límites superior e inferior del error.
• Estrategia de Precondicionamiento: La propuesta de utilizar ROR-BK como un pre-solucionador o iteración interna para acelerar la solución de sistemas mal condicionados sin la necesidad de precondicionadores externos explícitos y potencialmente inestables.

Resultos
Los autores realizaron extensos experimentos numéricos comparando ROR-BK contra:

• Solucionadores Aleatorios: Simple Orthogonal Block-Kaczmarz (SOBK) y Tail Averaged Regularized Block Kaczmarz (TA-ReBlocK-U).
• Solucionadores de Subespacio de Krylov: LSQR y varias variantes de GMRES (AB/BA-GMRES) con precondicionadores como Jacobi, ILU y Robust Incomplete Factorization (RIF).

Hallazgos de Desempeño:

• Velocidad e Iteraciones: A través de una amplia gama de matrices de prueba (incluyendo matrices dispersas de la colección de la Universidad de Florida y matrices densas generadas aleatoriamente), ROR-BK requirió consistentemente menos iteraciones y menos tiempo de CPU que SOBK y TA-ReBlocK-U. Las aceleraciones oscilaron entre 1.23x y 5.17x sobre SOBK y hasta 49.08x sobre TA-ReBlocK-U en términos de tiempo de CPU.
• Sistemas Mal Condicionados: En escenarios altamente mal condicionados (números de condición hasta $10^{20}$), muchos solucionadores de Krylov y sus versiones precondicionadas fallaron en converger dentro del límite de iteraciones o produjeron errores relativos grandes. ROR-BK logró converger con éxito en estos casos, logrando a menudo errores relativos más bajos.
• Aplicación en el Mundo Real: El método fue probado en problemas de reconstrucción de imágenes (tomografía de haz paralelo y MRI) que involucran datos ruidosos y sistemas severamente subdeterminados. ROR-BK demostró un desempeño superior en términos de Relación Señal-Ruido de Pico (PSNR) e Índice de Similitud Estructural (SSIM) en comparación con otros métodos, particularmente en escenarios donde otros solucionadores sufrieron de inestabilidad o falla.

Significancia y Reivindicaciones
El artículo afirma que ROR-BK ofrece una alternativa prometedora para resolver sistemas lineales donde la matriz $A$ está mal condicionada, logrando aproximaciones eficientes sin la necesidad de un precondicionamiento explícito. Los autores argumentan que, mientras que los precondicionadores pretenden reducir el número de condición de la matriz, no necesariamente reducen el número de condición del problema en sí y pueden introducir inestabilidad numérica. Al particionar el sistema en bloques y utilizar la ortogonalidad efectiva y la regularización, ROR-BK distribuye las ecuaciones covariantes en subproblemas potencialmente bien condicionados.

Los autores posicionan el método como un solucionador robusto para sistemas cuadrados, sobredeterminados y subdeterminados. Además, sugieren su utilidad como pre-solucionador o iteración interna para acelerar otros métodos iterativos como GMRES, particularmente en casos donde las técnicas de precondicionamiento estándar fallan debido a rupturas de pivote o deficiencia de rango. El trabajo enfatiza que la combinación de la dinámica basada en el residuo y el muestreo de ortogonalidad proporciona un mecanismo simple pero efectivo para una convergencia rápida y estable en sistemas lineales de alto número de condición.