Greedy randomized block Kaczmarz method for matrix equation AXB=C and its applications in color image restoration

Sintesi Tecnica: Metodo Kaczmarz a Blocchi Casuale e Greedy per l'equazione matriciale $AXB = C$ e Applicazioni nel Restauro di Immagini a Colori

Enunciato del Problema
Il documento affronta la risoluzione di equazioni matriciali su larga scala della forma $AXB = C$, dove $A \in \mathbb{R}^{m \times p}$, $B \in \mathbb{R}^{q \times n}$ e $C \in \mathbb{R}^{m \times n}$. Questa equazione sorge frequentemente in applicazioni ingegneristiche, tra cui l'elaborazione delle immagini, l'analisi della stabilità, la teoria del controllo e il regressione nel machine learning. Poiché i metodi diretti sono impraticabili per sistemi di grandi dimensioni, i metodi iterativi tradizionali (ad esempio, basati sul gradiente, Jacobi, Gauss-Seidel) richiedono spesso l'archiviazione e il calcolo con l'intera matrice dei coefficienti ad ogni passo, creando elevate richieste di memoria e computazionali. Gli autori si concentrano su metodi di azione riga e colonna, specificamente estendendo il metodo Kaczmarz, che evita l'accesso all'intera matrice operando su sottoblocchi.

Metodologia
Gli autori propongono una serie di algoritmi iterativi basati sulla struttura Kaczmarz, adattati per l'equazione matriciale $AXB = C$:

1. Kaczmarz a Blocchi (ME-BK): Un metodo ciclico deterministico in cui l'indice di riga $i_k$ viene selezionato sequenzialmente ($i_k = (k \mod m) + 1$). L'aggiornamento proietta la stima corrente sull'iperpiano definito dalla riga selezionata di $A$.
2. Kaczmarz a Blocchi Casuale e Greedy (ME-GRBK): Un metodo stocastico che seleziona le righe in base a un criterio di probabilità che favorisce quelle con residui maggiori. Nello specifico, definisce una soglia $\zeta_k$ basata sul massimo residuo normalizzato e sulla norma globale del residuo. Le righe che soddisfano $\|R_k^{i,:}\|_2^2 \ge \zeta_k \|A_{i,:}\|_2^2 \|R_k\|_F^2$ formano un insieme candidato $J_k$, dal quale viene scelta una riga con probabilità proporzionale al quadrato del suo residuo.
3. Kaczmarz a Blocchi Casuale e Greedy con Rilassamento (ME-RGRBK): Un'estensione di ME-GRBK che introduce un fattore di rilassamento $\theta \in (0, 1)$ nel criterio di probabilità per consentire una selezione più flessibile dell'insieme di indici.
4. Kaczmarz a Blocchi con Residuo Pesato Massimale (ME-MWRBK): Una versione deterministica di ME-GRBK che seleziona l'indice di riga che massimizza il residuo pesato $\frac{\|R_k^{i,:}\|_2^2}{\|A_{i,:}\|_2^2}$.

Gli algoritmi utilizzano implicitamente la struttura del prodotto di Kronecker (tramite vettorizzazione) e aggiornano la matrice del residuo $R_k = C - AX_kB$ in modo efficiente precalcolando $AA^T$ e $B^TB$.

Contributi Chiave

• Convergenza di ME-BK: Il documento stabilisce che il metodo deterministico ME-BK converge alla soluzione $X^* + X_0 - A^+AX_0BB^+$ (dove $X^* = A^+CB^+$ è l'unica soluzione a norma minima) quando il sistema è consistente. Ciò colma una lacuna, poiché la convergenza del metodo Kaczmarz a blocchi per $AXB=C$ non era stata precedentemente investigata.
• Convergenza delle Varianti Greedy: Gli autori dimostrano che i metodi ME-GRBK, ME-RGRBK e ME-MWRBK convergono alla soluzione unica a norma minima $A^+CB^+$ in valore atteso quando il sistema è consistente.
• Tassi di Convergenza: L'analisi teorica dimostra che i fattori di convergenza per i metodi greedy e rilassati sono strettamente minori (indicando una convergenza più rapida) rispetto a quello del metodo Kaczmarz a Blocchi Casuale (ME-RBK) esistente in [12].
• Distinzione dai Lavori Precedenti: Gli autori chiariscono che il loro approccio differisce dal metodo in [11]. Mentre [11] trasforma l'equazione in $mn$ sottosistemi richiedendo due indici stocastici, questo lavoro trasforma l'equazione in $m$ sottosistemi ($A_{i,:}XB = C_{i,:}$) richiedendo solo un indice stocastico per iterazione.

Risultati
Esperimenti numerici sono stati condotti utilizzando MATLAB su vari set di matrici (sparse e dense, a pieno rango e a rango deficitario) provenienti dalla collezione dell'Università della Florida e da generatori casuali.

• Verifica della Convergenza: La convergenza teorica di ME-BK alla specifica forma di soluzione è stata verificata attraverso sei set di matrici.
• Confronto delle Prestazioni: In termini di numero di iterazioni (IT) e tempo di CPU, i metodi proposti ME-GRBK, ME-RGRBK e ME-MWRBK hanno costantemente superato il metodo ME-RBK.
  • Per sistemi a pieno rango di colonna/riga, gli acceleramenti sono variati da circa 2x a 13x a seconda del set di matrici e del metodo.
  • Per sistemi a rango deficitario, gli acceleramenti sono variati da 1,35x a 4,29x.
  • Il metodo ME-MWRBK (deterministico) ha generalmente ottenuto gli acceleramenti più elevati, seguito da vicino da ME-RGRBK e ME-GRBK.
• Applicazione al Restauro di Immagini: I metodi sono stati applicati al restauro di immagini a colori (deblurring) modellato come $B = AXA_c^T + E$. Utilizzando immagini di test ("face", "bird", "mandril", "barbara"), i metodi proposti hanno raggiunto un rapporto Segnale-Rumore di Picco (PSNR) e un Indice di Similarità Strutturale (SSIM) significativamente più alti rispetto a ME-RBK. Ad esempio, sull'immagine "face", ME-RBK ha prodotto un PSNR di 27,02, mentre ME-MWRBK ha raggiunto 33,72.

Significatività
Il documento sostiene che i metodi proposti offrono un approccio più efficiente ed efficace per risolvere equazioni matriciali su larga scala $AXB=C$ rispetto ai metodi Kaczarc esistenti a blocchi casuali. Introducendo strategie di selezione greedy e varianti deterministiche, gli autori dimostrano tassi di convergenza superiori sia teoricamente che numericamente. La riuscita applicazione al restauro di immagini a colori valida l'utilità pratica di questi algoritmi in problemi ingegneristici reali dove i vincoli di dati su larga scala e di archiviazione sono critici. Il lavoro espande l'applicabilità dei metodi di tipo Kaczarc oltre i sistemi lineari verso equazioni matriciali generali.