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

Technische Samenvatting: Greedy Randomized Block Kaczmarz Methode voor de Matrixvergelijking $AXB = C$ en Toepassingen in Kleurenbeeldreconstructie

Probleemstelling
Het artikel behandelt de oplossing van grootschalige matrixvergelijkingen van de vorm $AXB = C$, waarbij $A \in \mathbb{R}^{m \times p}$, $B \in \mathbb{R}^{q \times n}$ en $C \in \mathbb{R}^{m \times n}$. Deze vergelijking komt veel voor in technische toepassingen, waaronder beeldverwerking, stabiliteitsanalyse, regeltheorie en machine learning regressie. Hoewel directe methoden onpraktisch zijn voor grootschalige systemen, vereisen traditionele iteratieve methoden (bijv. gradiëntgebaseerde, Jacobi, Gauss-Seidel) vaak het opslaan en berekenen van de volledige coëfficiëntmatrix bij elke stap, wat leidt tot hoge opslag- en computationele eisen. De auteurs richten zich op rij-actie en kolom-actie methoden, specifiek een uitbreiding van de Kaczmarz-methode, die geen volledige toegang tot de matrix vereist door te opereren op subblokken.

Methodologie
De auteurs stellen een reeks iteratieve algoritmen voor gebaseerd op het Kaczmarz-raamwerk, aangepast voor de matrixvergelijking $AXB = C$:

1. Block Kaczar (ME-BK): Een deterministische cyclische methode waarbij de rij-index $i_k$ sequentieel wordt geselecteerd ($i_k = (k \mod m) + 1$). De update projecteert de huidige schatting op het hypervlak gedefinieerd door de geselecteerde rij van $A$.
2. Greedy Randomized Block Kaczmarz (ME-GRBK): Een stochastische methode die rijen selecteert op basis van een probabilistisch criterium dat rijen met grotere residuen bevoordeelt. Specifiek definiëren zij een drempelwaarde $\zeta_k$ gebaseerd op het maximale genormaliseerde residu en de globale residunorm. Rijen die voldoen aan $\|R_k^{i,:}\|_2^2 \ge \zeta_k \|A_{i,:}\|_2^2 \|R_k\|_F^2$ vormen een kandidaatverzameling $J_k$, waaruit een rij wordt gekozen met een waarschijnlijkheid proportioneel aan het kwadraat van het residu.
3. Relaxed Greedy Randomized Block Kaczars (ME-RGRBK): Een uitbreiding van ME-GRBK die een relaxatiefactor $\theta \in (0, 1)$ introduceert in het probabilistische criterium om meer flexibele indexverzameling mogelijk te maken.
4. Maximal Weighted Residual Block Kaczars (ME-MWRBK): Een deterministische versie van ME-GRBK die de rij-index selecteert die het gewogen residu $\frac{\|R_k^{i,:}\|_2^2}{\|A_{i,:}\|_2^2}$ maximaliseert.

De algoritmen maken gebruik van de impliciete Kronecker-productstructuur (via vectorisatie) en updaten de residumatrix $R_k = C - AX_kB$ efficiënt door $AA^T$ en $B^TB$ voor te berekenen.

Belangrijkste Bijdragen

• Convergentie van ME-BK: Het artikel stelt vast dat de deterministische ME-BK methode convergeert naar de oplossing $X^* + X_0 - A^+AX_0BB^+$ (waarbij $X^* = A^+CB^+$ de unieke kleinste-norm oplossing is) wanneer het systeem consistent is. Dit vult een gat, aangezien de convergentie van de block Kaczars methode voor $AXB=C$ voorheen niet onderzocht was.
• Convergentie van Greedy Varianten: De auteurs bewijzen dat de ME-GRBK, ME-RGRBK en ME-MWRBK methoden in verwachting convergeren naar de unieke kleinste-norm oplossing $A^+CB^+$ wanneer het systeem consistent is.
• Convergentiesnelheden: Theoretische analyse toont aan dat de convergentiefactoren voor de greedy en relaxed methoden strikt kleiner zijn (wat wijst op snellere convergentie) dan die van de bestaande Randomized Block Kaczars (ME-RBK) methode gepresenteerd in [12].
• Onderscheid van Voorgaand Werk: De auteurs verduidelijken dat hun benadering verschilt van de methode in [11]. Terwijl [11] de vergelijking transformeert naar $mn$ subsystemen die twee stochastische indices vereisen, transformeert dit artikel het naar $m$ subsystemen ($A_{i,:}XB = C_{i,:}$) die slechts één stochastische index per iteratie vereisen.

Resultaten
Numerieke experimenten werden uitgevoerd met MATLAB op diverse matricesets (ijl en dicht, vol rank en rank-tekortschietend) uit de University of Florida collectie en willekeurige generatoren.

• Verificatie van Convergentie: De theoretische convergentie van ME-BK naar de specifieke oplossingsvorm werd geverifieerd over zes matricesets.
• Prestatievergelijking: Wat betreft iteratieaantal (IT) en CPU-tijd presteerden de voorgestelde ME-GRBK, ME-RGRBK en ME-MWRBK methoden consequent beter dan de ME-RBK methode.
  • Voor systemen met volledige kolom-/rij-rank varieerden de versnellingen van ongeveer 2x tot 13x, afhankelijk van de matriceset en methode.
  • Voor rank-tekortschietende systemen varieerden de versnellingen van 1.35x tot 4.29x.
  • De ME-MWRBK (deterministisch) behaalde over het algemeen de hoogste versnellingen, gevolgd door ME-RGRBK en ME-GRBK.
• Toepassing op Kleurenbeeldreconstructie: De methoden werden toegepast op kleurenbeeldreconstructie (deblurring) gemodelleerd als $B = AXA_c^T + E$. Met behulp van testbeelden ("face", "bird", "mandril", "barbara") bereikten de voorgestelde methoden een significant hogere Peak Signal-to-Noise Ratio (PSNR) en Structural Similarity Index (SSIM) vergeleken met ME-RBK. Bijvoorbeeld, op de "face" afbeelding leverde ME-RBK een PSNR van 27.02, terwijl ME-MWRBK 33.72 bereikte.

Betekenis
Het artikel beweert dat de voorgestelde methoden een efficiëntere en effectievere benadering bieden voor het oplossen van grootschalige matrixvergelijkingen $AXB=C$ vergeleken met bestaande randomized block Kaczars methoden. Door greedy selectiestrategieën en deterministische varianten te introduceren, demonstreren de auteurs superieure convergentiesnelheden zowel theoretisch als numeriek. De succesvolle toepassing op kleurenbeeldreconstructie valideert het praktische nut van deze algoritmen in reële engineeringproblemen waar grootschalige data en opslagbeperkingen kritieke factoren zijn. Het werk breidt de toepasbaarheid van Kaczars-type methoden uit van lineaire systemen naar algemene matrixvergelijkingen.