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

Probleemstelling
Het artikel behandelt de uitdaging van het oplossen van consistente lineaire stelsels van vergelijkingen $Ax = b$, waarbij $A \in \mathbb{R}^{m \times n}$ en $b \in \mathbb{R}^{m \times 1}$. De primaire focus ligt op stelsels die zeer slecht geconditioneerd zijn, inclusclusief ijle (sparse) systemen, dichte kleinste-kwadratenproblemen en gevallen die significant over- of onderbepaald zijn. De auteurs benadrukken dat standaard iteratieve methoden, zoals GMRES, vaak moeite hebben met deze systemen omdat het minimaliseren van de residu-norm niet noodzakelijkerwijs convergentie in de relatieve fout garandeert bij slecht geconditioneerde problemen. Bovendien kunnen traditionele preconditioning-technieken (bijv. ILU, Jacobi) lijden onder numerieke instabiliteit, pivot-breakdowns of excessieve fill-in wanneer ze worden toegepast op matrices met zeer grote condities, waardoor ze vaak falen precies wanneer robuuste acceleratie het hardst nodig is.

Methodologie
De auteurs stellen een verbeterd algoritme voor genaamd Regularized Orthogonality and Residual based Block-Kaczmarz (ROR-BK). Deze methode bouwt voort op het gerandomiseerde block-Kaczmarz-raamwerk, maar introduceert drie specifieke verbeteringen om stabiliteit en convergentie te verbeteren:

1. Dynamische Residue-gebaseerde Aggregatie: In plaats van uitsluitend te vertrouwen op vaste blokken, aggregeert de methode dynamisch een subset van vergelijkingen bij elke iteratie op basis van de huidige residuvector. Specifiek selecteert het rijen die het meest bijdragen aan het gekwadrateerde residu om een blok te vormen, met als doel de residu-norm in elke stap effectiever te minimaliseren.
2. Effectieve Wederzijdse Orthogonaliteits-sampling: De methode generaliseert het concept van orthogonaliteit tussen blokparen (gebruikt in de Simple Orthogonal Block-Kaczmarz of SOBK-methode) naar de "effectieve orthogonaliteit" van een enkel blok ten opzichte van alle andere blokken. Een symmetrische matrix $C$ wordt berekend waarbij de entries de cosinus van de effectieve hoek tussen blokcentroids vertegenwoordigen. Blokken worden vervolgens probabilistisch gesampled op basis van een distributie die blokken bevoordeelt met een hoge cumulatieve orthogonaliteit ten opzichte van de rest van het systeem.
3. Regularisatie: Om numerieke stabiliteit te waarborgen, met name wanneer blokken rangtekortig of slecht geconditioneerd zijn, maken de blok-updates gebruik van een geregulariseerde pseudo-inverse. In plaats van de standaard Moore-Penrose inverse $B^\dagger = B^T(BB^T)^{-1}$, gebruikt de methode de geregulariseerde vorm $B^T(BB^T + \mu I)^{-1}$, waarbij $\mu$ een kleine positieve constante is. Dit kan worden geïnterpreteerd als een stochastisch proximale punt-algoritme.

Het algoritme werkt door af te wisselen tussen updates met behulp van de orthogonaliteits-gesamplede blokken en updates met behulp van de residue-gebaseerde dynamische blokken. De auteurs demonstreren ook dat deze methode kan dienen als een innerlijke iteratie (preconditioner) voor flexibele GMRES (FAB-GMRES) solvers.

Belangrijkste Bijdragen

• Algoritmische Innovatie: De introductie van ROR-BK, die residue-gebaseerde dynamische blokselectie, global orthogonality-aware sampling en Tikhonov-stijl regularisatie combineert binnen een block-Kaczmarz-raamwerk.
• Theoretische Analyse: Het artikel biedt een convergentieanalyse (Theorema 2.3 en 2.4) die aantoont dat de methode stabiele convergentie bereikt, zelfs wanneer blokken numeriek rangtekortig zijn. Het stelt vast dat de foutreductie begrensd wordt door de regularisatieparameter $\mu$ en de kleinste niet-nul eigenwaarde van de blokmatrices. Theorem 2.4 beargumenteert verder dat het selecteren van blokken op basis van maximale residuen de boven- en ondergrenzen van de fout verbetert.
• Preconditioning Strategie: Het voorstel om ROR-BK te gebruiken als een pre-solver of innerlijke iteratie voor GMRES om de oplossing van slecht geconditioneerde systemen te versnellen zonder de noodzaak voor expliciete, potentieel instabiele, externe preconditioners.

Resultaten
De auteurs hebben uitgebreide numerieke experimenten uitgevoerd waarbij ROR-BK werd vergeleken met:

• Gerandomiseerde Solvers: Simple Orthogonal Block-Kaczmarz (SOBK) en Tail Averaged Regularized Block Kaczmarz (TA-ReBlocK-U).
• Krylov Subspace Solvers: LSQR en diverse GMRES-varianten (AB/BA-GMRES) met preconditioners zoals Jacobi, ILU en Robust Incomplete Factorization (RIF).

Prestatiebevindingen:

• Snelheid en Iteraties: Over een breed scala aan testmatrices (inclusclusief ijle matrices uit de University of Florida collectie en willekeurig gegenereerde dichte matrices), vereiste ROR-BK consequent minder iteraties en minder CPU-tijd dan SOBK en TA-ReBlocK-U. Versnellingen varieerden van 1,23x tot 5,17x over SOBK en tot 49,08x over TA-ReBlocK-U in termen van CPU-tijd.
• Slecht Geconditioneerde Systemen: In zeer slecht geconditioneerde scenario's (conditiegetallen tot $10^{20}$) faalden veel Krylov-solvers en hun gepreconditioneerde versies om te convergeren binnen de iteratielimiet of produceerden ze grote relatieve fouten. ROR-BK convergeerde succesvol in deze gevallen en bereikte vaak lagere relatieve fouten.
• Real-World Applicatie: De methode werd getest op beeldreconstructieproblemen (parallel-beam tomografie en MRI) met ruisende data en ernstig onderbepaalde systemen. ROR-BK demonstreerde superieure prestaties in termen van Peak Signal-to-Noise Ratio (PSNR) en Structural Similarity Index (SSIM) vergeleken met andere methoden, met name in scenario's waar andere solvers leden onder instabiliteit of falen.

Betekenis en Claims
Het artikel claimt dat ROR-BK een veelbelovend alternatief biedt voor het oplossen van lineaire systemen waarbij de matrix $A$ slecht geconditioneerd is, waarbij efficiënte benaderingen worden bereikt zonder de noodzaak van expliciete preconditioning. De auteurs betogen dat terwijl preconditioners beogen de conditie van de matrix te verminderen, ze niet noodzakelijkerwijs de conditie van het probleem zelf verminderen en numerieke instabiliteit kunnen introduceren. Door het systeem op te delen in blokken en gebruik te maken van effectieve orthogonaliteit en regularisatie, verdeelt ROR-BK de covariante vergelijkingen in potentieel goed geconditioneerde subproblemen.

De auteurs positioneren de methode als een robuuste solver voor vierkante, overbepaalde en onderbepaalde systemen. Ze suggereren verder de bruikbaarheid ervan als een pre-solver of innerlijke iteratie voor het versnellen van andere iteratieve methoden zoals GMRES, met name in gevallen waar standaard preconditioning-technieken falen door pivot-breakdowns of rangtekortigheid. Het werk benadrukt dat de combinatie van residue-gebaseerde dynamiek en orthogonaliteits-sampling een eenvoudige maar effectieve mechanisme biedt voor snelle en stabiele convergentie in lineaire systemen met een hoge conditie.