A Variational Equation and Lower Bound for the Linear Least-Squares Backward Error

Resumen Técnico: Una Ecuación Variacional y Cota Inferior para el Error Retroactivo de Mínimos Cuadrados Lineales

Enunciado del Problema
El artículo aborda el desafío de estimar eficientemente el error retroactivo, $\mu$, para problemas de mínimos cuadrados lineales con múltiples vectores de términos independientes:
$$\min_{X \in \mathbb{R}^{n \times d}} \|AX - B\|_F$$
donde $A \in \mathbb{R}^{m \times n}$ y $B \in \mathbb{R}^{m \times d}$. El error retroactivo $\mu$ se define como la norma mínima de las perturbaciones $[E, \theta F]$ tales que la solución aproximada $X$ se convierte en una solución exacta del sistema perturbado $(A+E)^T(A+E)X = (A+E)^T(B+F)$.

El cálculo directo de $\mu$ es prohibitivamente costoso para los solucionadores iterativos, ya que requiere resolver un problema de valores propios grande o un problema de valores propios generalizado. Aunque existen estimaciones (como la estimación de Karlson-Waldén), a menudo son costosas de calcular exactamente o carecen de cotas garantizadas (es decir, no son estrictamente cotas superiores o inferiores). El artículo busca un método para derivar estimaciones fiables y computacionalmente económicas, centrándose específicamente en cotas inferiores que puedan servir como criterios de parada para métodos iterativos como LSQR y LSMR.

Metodología
La metodología central se basa en expresar el error retroactivo en términos de un problema de valores propios generalizado dentro del marco del álgebra lineal indefinida.

1. Formulación Variacional: El artículo establece primero una ecuación variacional para el error retroactivo $\mu(A, R_\theta)$, donde $R_\theta$ es una matriz residual transformada. Expresa $\mu$ como un problema de maximización sobre una variedad indefinida definida por la restricción $X^T J_{n,d} X = -I_d$, donde $J_{n,d} = \text{diag}(I_n, -I_d)$.
   $$\mu(A, R_\theta) = \sup_{X^T J_{n,d} X = -I_d} \left( \|R_\theta\|_F^2 - \|[A, R_\theta]X\|_F^2 \right)^{1/2}$$
2. Descomposición CS Hiperbólica: Para resolver este problema de optimización, los autores utilizan la descomposición CS hiperbólica (un análogo indefinido de la descomposición CS para matrices unitarias). Esta descomposición permite desacoplar la optimización sobre la matriz $X$ en optimizaciones sobre matrices ortogonales y matrices de escalado diagonal.
3. Teorema de Descomposición: Al aplicar esta descomposición, el artículo deriva un teorema que muestra que el error retroactivo para un problema con $d$ vectores de términos independientes puede descomponerse en la suma de $d$ problemas de error retroactivo más pequeños, cada uno involucrando un único vector de términos independientes.
4. Construcción de Cota Inferior: Aprovechando esta descomposición, los autores proponen una cota inferior basada en sketching. Al calcular un único vector de prueba $p$ utilizando una matriz sketch $SA$ (donde $S$ es una matriz de sketching), pueden evaluar la fórmula de error retroactivo para un solo vector de términos independientes. Esto proporciona una cota inferior demostrable del error retroactivo verdadero.

Contribuciones Clave

• Teorema 1 (Descomposición): La contribución teórica principal es la descomposición del error retroactivo $\mu(A, R_\theta)$ en una suma de términos más pequeños:
  $$\mu(A, R_\theta) = \max_{P, Q} \left( \sum_{i=1}^k \mu^2(Ap_i, R_\theta q_i) \right)^{1/2}$$
  donde $P$ y $Q$ son matrices con columnas ortonormales. Esto reduce la complejidad del problema a una serie de optimizaciones escalares.
• Expresión Exacta para un Solo Vector de Términos Independientes: El artículo proporciona una expresión estable y de forma cerrada para el error retroactivo en el caso de un solo vector de términos independientes, $\mu(a, r)$, que depende de las normas de la suma y la diferencia de los vectores:
  $$\mu(a, r) = \frac{2|a^T r|}{\|a+r\|_2 + \|a-r\|_2}$$
• Cota Inferior Basada en Sketching: Los autores proponen una nueva cota inferior para métodos iterativos. Al utilizar una matriz de sketching $S$ para calcular una dirección aproximada $p$, pueden evaluar la fórmula de un solo vector de términos independientes para obtener un valor $\mu(Ap/\|p\|_2, r_\theta)$.
  • Este valor es demostrablemente una cota inferior del error retroactivo verdadero.
  • El artículo demuestra que esta cota inferior es de calidad comparable a la estimación de Karlson-Waldén basada en sketching, satisfaciendo específicamente la desigualdad:
    $$\frac{1-\eta^2}{1+\eta^2} \nu(A, r_\theta) \leq \mu(Ap/\|p\|_2, r_\theta) \leq \mu(A, r_\theta)$$
    donde $\eta$ representa la distorsión del sketch y $\nu$ es la estimación de Karlson-Waldén.
• Refinamiento Iterativo y Reutilización: El artículo discute métodos para mejorar esta estimación mediante el refinamiento iterativo del vector $p$ y la "reutilización" del vector calculado $Ap$ a través de las iteraciones para reducir el costo computacional.

Resultados
Se realizaron experimentos numéricos utilizando el solucionador LSMR sobre una matriz de la colección SuiteSparse con un número de condición alto ($\approx 3.5 \times 10^{16}$). Los resultados indican:

• La cota inferior propuesta es consistentemente comparable en precisión a la estimación de Karlson-Waldén basada en sketching.
• En casos con sketches más económicos (menor $n_{sketch}$), la cota inferior propuesta fue a veces más precisa que la estimación de Karlson-Waldén basada en sketching.
• La cota inferior "reutilizada" (reutilizando $Ap$ a través de las iteraciones) permaneció cerca del error retroactivo verdadero durante una parte significativa del historial de iteraciones, sugiriendo su utilidad como monitor de error económico.
• El refinamiento iterativo del vector $p$ mejoró la precisión solo cuando el tamaño del sketch fue muy grande ($16n$), lo que sugiere que para tamaños de sketch estándar, el costo computacional adicional podría no estar justificado.
• Los intentos de construir cotas superiores utilizando técnicas similares se encontraron que eran solo marginalmente mejores que las cotas simples existentes (como $\|A^T r\|_2 / \|r\|_2$) y aún sobreestimaban significativamente el error verdadero.

Significado y Afirmaciones
El artículo afirma que su principal significado es teórico: proporciona una descomposición del error retroactivo que conduce naturalmente a cotas inferiores computables.

• Fiabilidad: A diferencia de la estimación de Karlson-Waldén basada en sketching, que no está garantizada como cota superior o inferior, el método propuesto produce una cota inferior estricta. Esto es valioso para los criterios de parada, ya que garantiza que el error verdadero es al menos tan grande como la estimación.
• Eficiencia: El método permite la conversión de una estimación basada en sketching en una cota inferior de calidad comparable, pero con la garantía añadida de ser una cota.
• Modestia: Los autores son modestos respecto a las cotas superiores, señalando que sus intentos de producir cotas superiores de manera similar fueron "generalmente infructuosos". Reconocen que la descomposición para múltiples vectores de términos independientes implica optimizar sobre dos matrices ($P$ y $Q$), lo cual es más complejo que la optimización de un solo vector requerida para la cota inferior. Se sugiere trabajo futuro para abordar el caso de múltiples vectores de términos independientes e investigar por qué encontrar buenas cotas superiores parece más difícil que encontrar buenas cotas inferiores.