A Sketched Generalized Krylov Subspace Method for Large-Scale Regularization

Resumen Técnico: Un Método de Subespacio de Krylov Generalizado Esbozado para la Regularización a Gran Escala

Planteamiento del Problema
El artículo aborda problemas de mínimos cuadrados de gran escala y mal condicionados de la forma $\min_{x} \|Ax - b\|_2^2$, donde la matriz $A$ está severamente mal condicionada y $b$ contiene ruido. Para estabilizar la solución, se emplea la regularización de Tikhonov, lo que conduce al problema penalizado:
$$\min_{x \in \mathbb{R}^n} \left\{ \|Ax - b\|_2^2 + \lambda \|Lx\|_2^2 \right\},$$
donde $L$ es una matriz de regularización general que codifica información previa. Si bien existen métodos eficientes para la forma estándar de Tikhonov ($L=I$), el manejo de una $L$ general es computacionalmente desafiante. El método de Subespacio de Krylov Generalizado (GKS) [28] fue propuesto para manejar la $L$ general expandiendo un espacio de búsqueda utilizando el gradiente del funcional de Tikhonov. Sin embargo, a medida que la dimensión del subespacio crece, el GKS enfrenta dos cuellos de botella computacionales prohibitivos:

1. Factorizaciones QR Delgadas: Actualizar las factorizaciones QR de las matrices proyectadas $AV_k$ y $LV_k$ en cada iteración.
2. Reortogonalización: Reortogonalizar explícitamente los nuevos vectores de la base contra todas las columnas anteriores para mantener la estabilidad numérica, lo que requiere computaciones completas de productos internos.

Estas operaciones escalan de forma desfavorable con el número de iteraciones y el tamaño del problema, limitando la escalabilidad de GKS para problemas inversos a gran escala.

Metodología: GKS Esbozado (sGKS)
Los autores proponen sGKS, una variante aleatorizada del método GKS que utiliza el esbozo (sketching, reducción de dimensionalidad aleatorizada) para acelerar los pasos más costosos mientras preserva la calidad de la aproximación. La metodología se basa en dos observaciones primordiales:

1. Eliminación de la Reortogonalización Explícita: Los autores observan que el algoritmo GKS no depende intrínsecamente de la ortogonalidad de los vectores de la base para sus pasos centrales (a diferencia de los métodos de Krylov clásicos para sistemas lineales que dependen de las relaciones de Arnoldi/Lanczos). En consecuencia, sGKS omite la reortogonalización explícita de la base por completo. En lugar de mantener una base ortonormal $V_k$, sGKS mantiene una base no ortonormal $W_k$ formada por la anexión de los vectores de gradiente brutos. Esto elimina el costo de $O(d_k^2 n)$ de la reortogonalización (donde $d_k$ es la dimensión del subespacio).

2. Esbozo y Resolución para Problemas Proyectados: Para reducir el costo de resolver el problema de Tikhonov proyectado y actualizar las factorizaciones QR, sGKS emplea operadores de esbozo $S_A$ y $S_L$.

   • El problema de mínimos cuadrados proyectado se resuelve sobre matrices comprimidas $S_A A W_k$ y $S_L L W_k$ en lugar de las matrices completas $A W_k$ y $L W_k$.
   • Las factorizaciones QR se realizan sobre estas matrices esbozadas de tamaño $s \times d_k$ y se actualizan incrementalmente mediante extensiones de rango uno.
   • Los operadores de esbozo utilizados son Incrustaciones de Subespacio Obliviosas (específicamente, Transformadas Trigonométricas Submuestreadas Aleatorizadas, SRTT), que dependen únicamente de la dimensión del subespacio, no del subespacio mismo.

Contribuciones Clave

• Diseño Algorítmico: El desarrollo de sGKS, que integra el esbozo aleatorizado en el marco de trabajo de GKS para la regularización de Tikhonov de forma general.
• Análisis Teórico:
  • Equivalencia: Los autores demuestran que si se omite el esbozo en la resolución proyectada, sGKS produce iterados matemáticamente idénticos al GKS estándar (Proposición 1).
  • Cuasi-Optimalidad: Demuestran que cuando se aplica el esbozo, el método produce normas de residuo cuasi-óptimas, con el error controlado por la calidad de la incrustación ($\epsilon$) de los operadores de esbozo (Proposición 2).
  • Refinamiento Iterativo: Para los casos en que la pérdida de ortogonalidad de la base se vuelve significativa (llevando a una deficiencia de rango numérico), el artículo muestra que incorporar un pequeño número de pasos de refinamiento iterativo (IR) en la resolución proyectada restaura las propiedades espectrales de la base y recupera la precisión total del método sin esbozo.
• Eficiencia Computacional: El método reduce los costos por iteración al reemplazar las costosas actualizaciones de QR de rango completo y la reortogonalización por operaciones más económicas sobre matrices comprimidas.

Resultados Numéricos
El artículo evalúa sGKS en cuatro problemas inversos a gran escala:

1. Deblur de Imágenes: sGKS con diversas dimensiones de esbozo ($s$) logra una calidad de reconstrucción comparable al GKS estándar. Un $s$ mayor produce trayectorias de convergencia casi indistinguibles de GKS, mientras que un $s$ menor resulta en errores finales ligeramente mayores pero una convergencia más rápida.
2. Reconstrucción de CT de Rayos X: En un problema con $n=250,000$ incógnitas y un operador de regularización grande ($p \approx 500,000$), sGKS iguala la precisión de reconstrucción de GKS (RRE $\approx 0.183$) mientras reduce significativamente el tiempo de ejecución (wall-clock time). La aceleración es impulsada por la eliminación de la reortogonalización y la reducción de los costos de actualización de QR de $O(p)$ a $O(s)$.
3. Tomografía de Tiempo de Viaje Sísmica: En un sistema disperso y sobredeterminado, sGKS supera a los métodos híbridos de LSQR tanto en precisión como en velocidad. Aunque la aceleración sobre el GKS estándar es modesta aquí (ya que el cálculo del gradiente domina), sGKS aun así proporciona una reducción del 10% en el tiempo manteniendo una calidad de reconstrucción superior comparada con las variantes de LSQR.
4. CT Dinámico: En una formulación espacio-temporal con un operador de regularización masivo, los costos de QR y reortogonalización dominan el tiempo de ejecución del GKS estándar. Aquí, sGKS logra una aceleración de 3$\times$ sobre el GKS estándar. La inclusión de refinamiento iterativo (IR) permite que sGKS recupere la trayectoria de convergencia exacta y el parámetro de regularización óptimo del GKS sin esbozo, mientras que sGKS sin IR se estanca en un error ligeramente mayor.

Significancia y Afirmaciones
El artículo afirma que sGKS es una alternativa escalable al GKS estándar para la regularización a gran escala con matrices generales. Su importancia radica en:

• Escalabilidad: Elimina los cuellos de botella computacionales (reortogonalización y actualizaciones de QR de rango completo) que anteriormente limitaban la aplicabilidad de GKS a problemas muy grandes.
• Preservación de la Precisión: Mantiene la calidad de reconstrucción del método original, con garantías teóricas sobre las normas de residuo y evidencia empírica que muestra que el refinamiento iterativo puede recuperar la precisión total incluso cuando se pierde la ortogonalidad de la base.
• Generalidad: El enfoque es independiente de la elección específica del operador de esbozo y se aplica a matrices de regularización generales $L$, no solo a problemas de forma estándar.

Los autores concluyen que, si bien el método introduce un parámetro de esbozo ($s$) para ajustar el equilibrio entre velocidad y precisión, ofrece un marco robusto para resolver problemas inversos a gran escala donde los métodos de proyección estándar son computacionalmente prohibitivos. El trabajo futuro sugerido incluye la selección adaptativa de la dimensión del esbozo y extensiones a problemas inversos no lineales.