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

Sintesi Tecnica: Un'Equazione Variazionale e un Limite Inferiore per l'Errore Retrospettivo dei Minimi Quadrati Lineari

Enunciato del Problema
Il documento affronta la sfida di stimare in modo efficiente l'errore retrospettivo, $\mu$, per problemi di minimi quadrati lineari con più vettori di termine noto:
$$\min_{X \in \mathbb{R}^{n \times d}} \|AX - B\|_F$$
dove $A \in \mathbb{R}^{m \times n}$ e $B \in \mathbb{R}^{m \times d}$. L'errore retrospettivo $\mu$ è definito come la norma minima delle perturbazioni $[E, \theta F]$ tali che la soluzione approssimata $X$ diventi una soluzione esatta del sistema perturbato $(A+E)^T(A+E)X = (A+E)^T(B+F)$.

Il calcolo diretto di $\mu$ è proibitivamente costoso per i solver iterativi poiché richiede la risoluzione di un grande problema agli autovalori o di un problema generalizzato agli autovalori. Sebbene esistano stime (come la stima di Karlson-Waldén), queste sono spesso costose da calcolare esattamente o mancano di limiti garantiti (ovvero, non sono strettamente limiti superiori o inferiori). Il documento cerca un metodo per derivare stime affidabili e computazionalmente economiche, focalizzandosi specificamente sui limiti inferiori che possono servire come criteri di arresto per metodi iterativi come LSQR e LSMR.

Metodologia
La metodologia fondamentale si basa sull'espressione dell'errore retrospettivo in termini di un problema generalizzato agli autovalori nell'ambito dell'algebra lineare indefinita.

1. Formulazione Variazionale: Il documento stabilisce inizialmente un'equazione variazionale per l'errore retrospettivo $\mu(A, R_\theta)$, dove $R_\theta$ è una matrice del residuo trasformata. Esprime $\mu$ come un problema di massimizzazione su una varietà indefinita definita dal vincolo $X^T J_{n,d} X = -I_d$, dove $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. Decomposizione CS Ipertbolica: Per risolvere questo problema di ottimizzazione, gli autori utilizzano la decomposizione CS iperbolica (un analogo indefinito della decomposizione CS per matrici unitarie). Questa decomposizione permette di disaccoppiare l'ottimizzazione sulla matrice $X$ in ottimizzazioni su matrici ortogonali e matrici di scalatura diagonale.
3. Teorema di Decomposizione: Applicando tale decomposizione, il documento deriva un teorema che mostra come l'errore retrospettivo per un problema con $d$ vettori di termine noto possa essere scomposto nella somma di $d$ problemi di errore retrospettivo più piccoli, ciascuno coinvolgente un singolo vettore di termine noto.
4. Costruzione del Limite Inferiore: Sfruttando questa decomposizione, gli autori propongono un limite inferiore basato sullo sketching. Calcolando un singolo vettore di prova $p$ utilizzando una matrice skettata $SA$ (dove $S$ è una matrice di sketching), è possibile valutare la formula dell'errore retrospettivo per un singolo vettore di termine noto. Ciò fornisce un limite inferiore dimostrabile sull'errore retrospettivo vero.

Contributi Chiave

• Teorema 1 (Decomposizione): Il contributo teorico principale è la decomposizione dell'errore retrospettivo $\mu(A, R_\theta)$ in una somma di termini più piccoli:
  $$\mu(A, R_\theta) = \max_{P, Q} \left( \sum_{i=1}^k \mu^2(Ap_i, R_\theta q_i) \right)^{1/2}$$
  dove $P$ e $Q$ sono matrici con colonne ortonormali. Ciò riduce la complessità del problema a una serie di ottimizzazioni scalari.
• Espressione Esatta per Singolo Vettore di Termine Noto: Il documento fornisce un'espressione stabile e in forma chiusa per l'errore retrospettivo nel caso di singolo vettore di termine noto, $\mu(a, r)$, che dipende dalle norme della somma e della differenza dei vettori:
  $$\mu(a, r) = \frac{2|a^T r|}{\|a+r\|_2 + \|a-r\|_2}$$
• Limite Inferiore Basato su Sketching: Gli autori propongono un nuovo limite inferiore per i metodi iterativi. Utilizzando una matrice di sketching $S$ per calcolare una direzione approssimata $p$, è possibile valutare la formula per un singolo vettore di termine noto per ottenere un valore $\mu(Ap/\|p\|_2, r_\theta)$.
  • Questo valore è dimostrabilmente un limite inferiore sull'errore retrospettivo vero.
  • Il documento dimostra che questo limite inferiore è di qualità paragonabile alla stima di Karlson-Waldén skettata, soddisfacendo specificamente la disuguaglianza:
    $$\frac{1-\eta^2}{1+\eta^2} \nu(A, r_\theta) \leq \mu(Ap/\|p\|_2, r_\theta) \leq \mu(A, r_\theta)$$
    dove $\eta$ rappresenta la distorsione dello sketch e $\nu$ è la stima di Karlson-Waldén.
• Raffinamento Iterativo e Riciclo: Il documento discute metodi per migliorare questa stima attraverso il raffinamento iterativo del vettore $p$ e il "riciclo" del vettore calcolato $Ap$ tra le iterazioni per ridurre il costo computazionale.

Risultati
Sono stati condotti esperimenti numerici utilizzando il solver LSMR su una matrice della collezione SuiteSparse con un numero di condizione elevato ($\approx 3.5 \times 10^{16}$). I risultati indicano:

• Il limite inferiore proposto è costantemente paragonabile in accuratezza alla stima di Karlson-Waldén skettata.
• Nei casi con sketch più economici (piccolo $n_{sketch}$), il limite inferiore proposto è stato talvolta più accurato della stima di Karlson-Waldén skettata.
• Il limite inferiore "riciclato" (riutilizzando $Ap$ tra le iterazioni) è rimasto vicino all'errore retrospettivo vero per una porzione significativa della storia delle iterazioni, suggerendo utilità come monitor di errore economico.
• Il raffinamento iterativo del vettore $p$ ha migliorato l'accuratezza solo quando la dimensione dello sketch era molto grande ($16n$), suggerendo che per dimensioni di sketch standard, il costo computazionale aggiuntivo potrebbe non essere giustificato.
• I tentativi di costruire limiti superiori utilizzando tecniche simili sono risultati solo marginalmente migliori dei limiti semplici esistenti (come $\|A^T r\|_2 / \|r\|_2$) e hanno comunque sovrastimato significativamente l'errore vero.

Significato e Affermazioni
Il documento afferma che il suo significato principale è teorico: fornisce una decomposizione dell'errore retrospettivo che porta naturalmente a limiti inferiori calcolabili.

• Affidabilità: A differenza della stima di Karlson-Waldén skettata, che non è garantita essere un limite superiore o inferiore, il metodo proposto produce un limite inferiore rigoroso. Ciò è prezioso per i criteri di arresto, poiché garantisce che l'errore vero sia almeno grande quanto la stima.
• Efficienza: Il metodo permette la conversione di una stima basata su sketch in un limite inferiore di qualità paragonabile, ma con la garanzia aggiuntiva di essere un limite.
• Modestia: Gli autori sono modesti riguardo ai limiti superiori, notando che i loro tentativi di produrre limiti superiori in modo simile sono stati "generalmente infruttuosi". Riconoscono che la decomposizione per più vettori di termine noto implica l'ottimizzazione su due matrici ($P$ e $Q$), che è più complessa dell'ottimizzazione su un singolo vettore richiesta per il limite inferiore. Si suggerisce un lavoro futuro per affrontare il caso di più vettori di termine noto e per indagare perché trovare buoni limiti superiori sembri più difficile che trovare buoni limiti inferiori.