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

Enunciato del Problema
Il documento affronta la sfida di risolvere sistemi di equazioni lineari coerenti $Ax = b$, dove $A \in \mathbb{R}^{m \times n}$ e $b \in \mathbb{R}^{m \times 1}$. Il focus primario sono i sistemi altamente mal condizionati, inclusi i sistemi sparsi, i problemi di minimi quadrati densi e i casi significativamente sovradeterminati o sottodeterminati. Gli autori evidenziano come i metodi iterativi standard, come GMRES, spesso fatichino con questi sistemi perché la minimizzazione della norma del residuo non garantisce necessariamente la convergenza nell'errore relativo per problemi mal condizionati. Inoltre, le tecniche di precondizionamento tradizionali (ad esempio, ILU, Jacobi) possono soffrire di instabilità numerica, breakdown dei pivot o eccessivo riempimento (fill-in) quando applicate a matrici con numeri di condizionamento molto elevati, fallendo proprio quando è necessaria una robusta accelerazione.

Metodologia
Gli autori propongono un algoritmo potenziato denominato Regularized Orthogonality and Residual based Block-Kaczmarz (ROR-BK). Questo metodo si basa sul framework Kaczmarz a blocchi randomizzato, ma introduce tre miglioramenti specifici per migliorare la stabilità e la convergenza:

1. Aggregazione Dinamica Basata sul Residuo: Invece di fare affidamento esclusivamente su blocchi fissi, il metodo aggrega dinamicamente un sottoinsieme di equazioni a ogni iterazione in base all'attuale vettore residuo. Nello specifico, seleziona le righe che contribuiscono maggiormente al residuo al quadrato per formare un blocco, con l'obiettivo di minimizzare la norma del residuo in modo più efficace in ogni passaggio.
2. Campionamento dell'Ortogonalità Effettiva Mutua: Il metodo generalizza il concetto di ortogonalità tra coppie di blocchi (utilizzato nel metodo Simple Orthogonal Block-Kaczmarz o SOBK) all' "ortogonalità effettiva" di un singolo blocco rispetto a tutti gli altri blocchi. Viene calcolata una matrice simmetrica $C$ dove le voci rappresentano il coseno dell'angolo effettivo tra i centroidi dei blocchi. I blocchi vengono quindi campionati probabilisticamente in base a una distribuzione che favorisce i blocchi con alta ortogonalità cumulativa rispetto al resto del sistema.
3. Regolarizzazione: Per garantire la stabilità numerica, in particolare quando i blocchi sono a rango deficiente o mal condizionati, gli aggiornamenti dei blocchi utilizzano una pseudo-inversa regolarizzata. Invece della standard inversa di Moore-Penrose $B^\dagger = B^T(BB^T)^{-1}$, il metodo utilizza la forma regolarizzata $B^T(BB^T + \mu I)^{-1}$, dove $\mu$ è una piccola costante positiva. Ciò è interpretato come un algoritmo del punto prossimale stocastico.

L'algoritzza opera alternando tra aggiornamenti utilizzando i blocchi campionati per ortogonalità e aggiornamenti utilizzando i blocchi dinamici basati sul residuo. Gli autori dimostrano inoltre che questo metodo può servire come iterazione interna (precondizionatore) per i solutori GMRES flessibili (FAB-GMRES).

Contributi Chiave

• Innovazione Algoritmica: L'introduzione di ROR-BK, che combina la selezione dinamica dei blocchi basata sul residuo, il campionamento consapevole dell'ortogonalità globale e la regolarizzazione di tipo Tikhonov all'interno di un framework Block-Kaczmarz.
• Analisi Teorica: Il documento fornisce un'analisi della convergenza (Teoremi 2.3 e 2.4) mostrando che il metodo raggiunge una convergenza stabile anche quando i blocchi sono numericamente a rango deficiente. Stabilisce che la riduzione dell'errore è limitata dal parametro di regolarizzazione $\mu$ e dal più piccolo autovalore non nullo delle matrici dei blocchi. Il Teorema 2.4 sostiene ulteriormente che la selezione dei blocchi basata sui residui massimi migliora i limiti superiori e inferiori dell'errore.
• Strategia di Precondizionamento: La proposta di utilizzare ROR-BK come pre-solutore o iterazione interna per accelerare la soluzione di sistemi mal condizionati senza la necessità di precondizionatori esterni espliciti e potenzialmente instabili.

Risultati
Gli autori hanno condotto estesi esperimenti numerici confrontando ROR-BK con:

• Solutori Randomizzati: Simple Orthogonal Block-Kaczmarz (SOBK) e Tail Averaged Regularized Block Kaczmarz (TA-ReBlocK-U).
• Solutori di Sottospazio di Krylov: LSQR e varie varianti di GMRES (AB/BA-GMRES) con precondizionatori come Jacobi, ILU e Robust Incomplete Factorization (RIF).

Risultanze sulle Prestazioni:

• Velocità e Iterazioni: In una vasta gamma di matrici di test (inclusi matrici sparse dalla collezione dell'Università della Florida e matrici dense generate casualmente), ROR-BK ha richiesto costantemente meno iterazioni e meno tempo di CPU rispetto a SOBK e TA-ReBlocK-U. Gli acceleramenti sono variati da 1,23x a 5,17x rispetto a SOBK e fino a 49,08x rispetto a TA-ReBlocK-U in termini di tempo di CPU.
• Sistemi Mal Condizionati: In scenari altamente mal condizionati (numeri di condizionamento fino a $10^{20}$), molti solutori Krylov e le loro versioni precondizionate sono falliti nel convergere entro il limite di iterazioni o hanno prodotto errori relativi elevati. ROR-BK è riuscito a convergere in questi casi, ottenendo spesso errori relativi inferiori.
• Applicazione nel Mondo Reale: Il metodo è stato testato su problemi di ricostruzione d'immagine (tomografia a fascio parallelo e MRI) che coinvolgono dati rumorosi e sistemi severamente sottodeterminati. ROR-BK ha dimostrato prestazioni superiori in termini di Peak Signal-to-Noise Ratio (PSNR) e Structural Similarity Index (SSIM) rispetto ad altri metodi, particolarmente in scenari in cui altri solutori soffrivano di instabilità o fallimento.

Significatività e Rivendicazioni
Il documento afferma che ROR-BK offre un'alternativa promettente per risolvere sistemi lineari in cui la matrice $A$ è mal condizionata, ottenendo approssimazioni efficienti senza la necessità di un precondizionamento esplicito. Gli autori sostengono che, mentre i precondizionatori mirano a ridurre il numero di condizionamento della matrice, essi non riducono necessariamente il numero di condizionamento del problema stesso e possono introdurre instabilità numerica. Partizionando il sistema in blocchi e utilizzando l'ortogonalità effettiva e la regolarizzazione, ROR-BK distribuisce le equazioni covarianti in sottoproblemi potenzialmente ben condizionati.

Gli autori posizionano il metodo come un solutore robusto per sistemi quadrati, sovradeterminati e sottodeterminati. Suggeriscono inoltre la sua utilità come pre-solutore o iterazione interna per accelerare altri metodi iterativi come GMRES, in particolare nei casi in cui le tecniche di precondizionamento standard falliscono a causa di breakdown dei pivot o rango deficiente. Il lavoro sottolinea come la combinazione di dinamiche basate sul residuo e campionamento dell'ortogonalità fornisca un meccanismo semplice ma efficace per una convergenza rapida e stabile in sistemi lineari ad alto numero di condizionamento.