A Sketched Generalized Krylov Subspace Method for Large-Scale Regularization

Sintesi Tecnica: Un Metodo di Sottospazio di Krylov Generalizzato "Sketched" per la Regolarizzazione su Grande Scala

Definizione del Problema
Il documento affronta problemi di minimi quadrati mal posti su larga scala della forma $\min_{x} \|Ax - b\|_2^2$, dove la matrice $A$ è severamente mal condizionata e $b$ è contaminata da rumore. Per stabilizzare la soluzione, viene impiegata la regolarizzazione di Tikhonov, che porta al problema penalizzato:
$$\min_{x \in \mathbb{R}^n} \left\{ \|Ax - b\|_2^2 + \lambda \|Lx\|_2^2 \right\},$$
dove $L$ è una matrice di regolarizzazione generale che codifica informazioni a priori. Sebbene esistano metodi efficienti per la forma standard di Tikhonov ($L=I$), la gestione di un $L$ generale è computazionalmente impegnativa. Il metodo Generalized Krylov Subspace (GKS) [28] è stato proposto per gestire il caso di $L$ generale espandendo uno spazio di ricerca tramite il gradiente del funzionale di Tikhonov. Tuttavia, man mano che la dimensione del sottospazio cresce, il GKS affronta due colli di bottiglia computazionali proibitivi:

1. Fattorizzazioni QR sottili: l'aggiornamento delle fattorizzazioni QR delle matrici proiettate $AV_k$ e $LV_k$ ad ogni iterazione.
2. Riorogonalizzazione: la ri-ortogonalizzazione esplicita dei nuovi vettori base rispetto a tutte le colonne precedenti per mantenere la stabilità numerica, il che richiede calcoli completi di prodotto interno.

Queste operazioni scalano in modo sfavorevole rispetto al numero di iterazioni e alla dimensione del problema, limitando la scalabilità del GKS per problemi inversi su larga scala.

Metodologia: sGKS (Sketched GKS)
Gli autori propongono sGKS, una variante randomizzata del metodo GKS, che utilizza lo sketching (riduzione della dimensionalità randomizzata) per accelerare i passaggi più dispendiosi preservando la qualità dell'approssimazione. La metodologia si basa su due osservazioni primarie:

1. Eliminazione della Riorogonalizzazione Esplicita: Gli autori osservano che l'algoritmo GKS non si affida intrinsecamente all'ortogonalità dei vettori base per i suoi passaggi fondamentali (a differenza dei classici metodi di Krylov per sistemi lineari che si basano sulle relazioni di Arnoldi/Lanczos). Di conseguenza, sGKS salta completamente la rioralizzazione esplicita della base. Inveve di mantenere una base ortonormale $V_k$, sGKS mantiene una base non ortonormale $W_k$ formata dall'appendere i vettori gradiente grezzi. Ciò rimuove il costo di $O(d_k^2 n)$ della rioralizzazione (dove $d_k$ è la dimensione del sottospazio).

2. Sketch-and-Solve per Problemi Proiettati: Per ridurre il costo della risoluzione del problema di Tikhonov proiettato e l'aggiornamento delle fattorizzazioni QR, sGKS impiega operatori di sketching $S_A$ e $S_L$.

   • Il problema di minimi quadrati proiettato viene risolto su matrici compresse $S_A A W_k$ e $S_L L W_k$ anziché sulle matrici complete $A W_k$ e $L W_k$.
   • Le fattorizzazioni QR vengono eseguite su queste matrici "sketched" di dimensione $s \times d_k$ (dove $s \ll m, p$) e aggiornate incrementalmente tramite estensioni di rango uno.
   • Gli operatori di sketching utilizzati sono Oblivious Subspace Embeddings (specificamente Subsampled Randomized Trigonometric Transforms, SRTT), che dipendono solo dalla dimensione del sottospazio, non dal sottospazio stesso.

Contributi Chiave

• Design Algoritmico: Lo sviluppo di sGKS, che integra lo sketching randomizzato nel framework GKS per la regolarizzazione di Tikhonov a forma generale.
• Analisi Teorica:
  • Equivalenza: Gli autori dimostrano che se lo sketching viene omesso nella risoluzione proiettata, sGKS produce iterati matematicamente identici al GKS standard (Proposizione 1).
  • Quasi-Ottimalità: Dimostrano che, quando viene applicato lo sketching, il metodo produce norme residue quasi ottimali, con l'errore controllato dalla qualità dell'embedding ($\epsilon$) degli operatori di sketching (Proposizione 2).
  • Raffinamento Iterativo: Per i casi in cui la perdita di ortogonalità della base diventa significativa (portando a una scarsa densità di rango numerico), il documento mostra come l'incorporazione di un piccolo numero di passaggi di raffinamento iterativo (IR) nella risoluzione proiettata ripristini le proprietà spettrali della base e recuperi la piena accuratezza del metodo non-sketched.
• Efficienza Computazionale: Il metodo riduce i costi per iterazione sostituendo gli costosi aggiornamenti QR a pieno rango e la rioralizzazione con operazioni più economiche su matrici compresse.

Risultati Numerici
Il documento valuta sGks su quattro problemi inversi su larga scala:

1. Deblurring di Immagini: sGKS con varie dimensioni di sketch ($s$) raggiunge una qualità di ricostruzione comparabile al GKS standard. Un $s$ più grande produce traiettorie di convergenza quasi indistinguibili dal GKS, mentre un $s$ più piccolo risulta in errori finali leggermente superiori ma una convergenza più veloce.
2. Ricostruzione CT a raggi X: Su un problema con $n=250.000$ incognite e un operatore di regolarizzazione ampio ($p \approx 500.000$), sGKS eguaglia l'accuratezza di ricostruzione del GKS (RRE $\approx 0.183$) riducendo significativamente il tempo di esecuzione (wall-clock time). L'accelerazione è guidata dall'eliminazione della rioralizzazione e dalla riduzione dei costi di aggiornamento QR da $O(p)$ a $O(s)$.
3. Tomografia del Tempo di Viaggio Sismico: Su un sistema sparso e sovradeterminato, sGKS supera i metodi ibridi LSQR sia in accuratezza che in velocità. Sebbene l'accelerazione rispetto al GKS standard sia modesta qui (poiché il calcolo del gradiente domina), sGKS fornisce comunque una riduzione del tempo del 10% mantenendo una qualità di ricostruzione superiore rispetto alle varianti LSQR.
4. CT Dinamica: In una formulazione spazio-temporale con un operatore di regolarizzazione massiccio, i costi di QR e rioralizzazione dominano il runtime del GKS standard. In questo caso, sGKS ottiene un'accelerazione di 3× rispetto al GKS standard. L'inclusione del raffinamento iterativo (IR) consente a sGKS di recuperare la traiettoria di convergenza esatta e il parametro di regolarizzazione ottimale del GKS non-sketched, mentre sGKS senza IR ristagna a un errore leggermente superiore.

Significatività e Rivendicazioni
Il documento afferma che sGKS è un'alternativa scalabile al GKS standard per la regolarizzazione su larga scala con matrici generali. La sua importanza risiede in:

• Scalabilità: Rimuove i colli di bottiglia computazionali (rioralizzazione e aggiornamenti QR a pieno rango) che precedentemente limitavano l'applicabilità del GKS a problemi molto grandi.
• Preservazione dell'Accuratezza: Mantiene la qualità di ricostruzione del metodo originale, con garanzie teoriche sulle norme residue e prove empiriche che mostrano come il raffinamento iterativo possa recuperare la piena accuratezza anche quando l'ortogonalità della base viene persa.
• Generalità: L'approccio è indipendente dalla scelta specifica dell'operatore di sketching e si applica a matrici di regolarizzazione generali, non solo ai problemi in forma standard.

Gli autori concludono che, sebbene il metodo introduca un parametro di sketching ($s$) per regolare il compromesso tra velocità e accuratezza, esso offre un framework robusto per risolvere problemi inversi su larga scala dove i metodi di proiezione standard sono computazionalmente proibitivi. Il lavoro futuro suggerito include la selezione adattiva della dimensione dello sketch ed estensioni ai problemi inversi non lineari.