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

Problemstellung
Die Arbeit befasst sich mit der Herausforderung, konsistente lineare Gleichungssysteme der Form $Ax = b$ zu lösen, wobei $A \in \mathbb{R}^{m \times n}$ und $b \in \mathbb{R}^{m \times 1}$. Der primäre Fokus liegt auf Systemen, die hochgradig schlecht konditioniert sind, einschließlich dünnbesetzter (sparse) Systeme, dichter Kleinste-Quadrate-Probleme sowie Fällen, die signifikant über- oder unterbestimmt sind. Die Autoren heben hervor, dass Standard-Iterationsverfahren wie GMRES bei diesen Systemen oft Schwierigkeiten haben, da die Minimierung der Residuennorm nicht zwangsläufig eine Konvergenz des relativen Fehlers bei schlecht konditionierten Problemen garantiert. Zudem können traditionelle Präkonditionierungstechniken (z. B. ILU, Jacobi) bei Matrizen mit sehr großen Konditionszahlen zu numerischer Instabilität, Pivot-Breakdowns oder übermäßigem Fill-in führen und genau dann versagen, wenn eine robuste Beschleunigung am dringendsten benötigt wird.

Methodik
Die Autoren schlagen einen verbesserten Algorithmus namens Regularized Orthogonality and Residual based Block-Kaczmarz (ROR-BK) vor. Diese Methode baut auf dem randomisierten Block-Kaczmarz-Framework auf, führt jedoch drei spezifische Erweiterungen ein, um Stabilität und Konvergenz zu verbessern:

1. Dynamische residuenbasierte Aggregation: Anstatt sich ausschließlich auf feste Blöcke zu verlassen, aggregiert die Methode in jeder Iteration dynamisch eine Teilmenge von Gleichungen basierend auf dem aktuellen Residuenvektor. Konkret werden Zeilen ausgewählt, die am stärksten zum quadrierten Residuum beitragen, um einen Block zu bilden, mit dem Ziel, die Residuennorm in jedem Schritt effektiver zu minimieren.
2. Effektive gegenseitige Orthogonalitäts-Abtastung (Sampling): Die Methode verallgemeinert das Konzept der Orthogonalität zwischen Blockpaaren (verwendet in der Simple Orthogonal Block-Kaczmarz oder SOBK Methode) auf die „effektive Orthogonalität“ eines einzelnen Blocks gegenüber allen anderen Blöcken. Es wird eine symmetrische Matrix $C$ berechnet, deren Einträge den Kosinus des effektiven Winkels zwischen den Block-Zentroiden darstellen. Blöcke werden dann probabilistisch basierend auf einer Verteilung abgetastet, die Blöcke bevorzugt, die eine hohe kumulative Orthogonalität zum restlichen System aufweisen.
3. Regularisierung: Um die numerische Stabilität zu gewährleisten, insbesondere wenn Blöcke rangdefizient oder schlecht konditioniert sind, nutzen die Block-Updates eine regularisierte Pseudoinverse. Anstatt der Standard-Moore-Penrose-Inversen $B^\dagger = B^T(BB^T)^{-1}$ verwendet die Methode die regularisierte Form $B^T(BB^T + \mu I)^{-1}$, wobei $\mu$ eine kleine positive Konstante ist. Dies wird als stochastischer proximaler Punkt-Algorithmus interpretiert.

Der Algorithmus arbeitet durch den Wechsel zwischen Updates unter Verwendung der orthogonalitätsbasierten Abtastblöcke und Updates unter Verwendung der residuenbasierten dynamischen Blöcke. Die Autoren zeigen zudem, dass diese Methode als innere Iteration (Präkonditionierer) für flexible GMRES-Löser (FAB-GMRES) dienen kann.

Zentrale Beiträge

• Algorithmische Innovation: Die Einführung von ROR-BK, das residuenbasierte dynamische Block-Selection, globale Orthogonalitäts-bewusste Abtastung und Tikhonov-artige Regularisierung innerhalb eines Block-Kaczmarz-Frameworks kombiniert.
• Theoretische Analyse: Die Arbeit liefert eine Konvergenzanalyse (Theoreme 2.3 und 2.4), die zeigt, dass die Methode selbst dann eine stabile Konvergenz erreicht, wenn Blöcke numerisch rangdefizient sind. Sie stellt fest, dass die Fehlerminimierung durch den Regularisierungsparameter $\mu$ und den kleinsten nicht-null Eigenwert der Blockmatrizen begrenzt wird. Theorem 2.4 argumentiert weiter, dass die Auswahl von Blöcken basierend auf maximalen Residuen die oberen und unteren Fehlergrenzen verbessert.
• Präkonditionierungsstrategie: Der Vorschlag, ROR-BK als Pre-Solver oder innere Iteration für GMRES einzusetzen, um die Lösung schlecht konditionierter Systeme zu beschleunigen, ohne die Notwendigkeit expliziter, potenziell instabiler externer Präkonditionierer.

Ergebnisse
Die Autoren führten umfangreiche numerische Experimente durch, bei denen ROR-BK gegen folgende Verfahren getestet wurde:

• Randomisierte Solver: Simple Orthogonal Block-Kaczmarz (SOBK) und Tail Averaged Regularized Block Kaczmarz (TA-ReBlocK-U).
• Krylov-Unterraum-Solver: LSQR und verschiedene GMRES-Varianten (AB/BA-GMRES) mit Präkonditionierern wie Jacobi, ILU und Robust Incomplete Factorization (RIF).

Leistungsbefunde:

• Geschwindigkeit und Iterationen: Über eine breite Palette von Testmatrizen hinweg (einschließlich dünnbesetzter Matrizen aus der University of Florida Collection und zufällig generierter dichter Matrizen) benötigte ROR-BK konsistent weniger Iterationen und weniger CPU-Zeit als SOBK und TA-ReBlocK-U. Die Beschleunigungen reichten von 1,23x bis 5,17x gegenüber SOBK und bis zu 49,08x gegenüber TA-ReBlocK-U in Bezug auf die CPU-Zeit.
• Schlecht konditionierte Systeme: In hochgradig schlecht konditionierten Szenarien (Konditionszahlen bis zu $10^{20}$) versagten viele Krylov-Solver und deren präkonditionierte Versionen, indem sie entweder innerhalb des Iterationslimits nicht konvergierten oder große relative Fehler produzierten. ROR-BK konvergierte in diesen Fällen erfolgreich und erreichte oft geringere relative Fehler.
• Reale Anwendungen: Die Methode wurde auf Bildrekonstruktionsprobleme (Parallelstrahl-Tomographie und MRT) mit verrauschten Daten und schwer unterbestimmten Systemen angewendet. ROR-BK zeigte eine überlegene Leistung hinsichtlich des Peak Signal-to-Noise Ratio (PSNR) und des Structural Similarity Index (SSIM) im Vergleich zu anderen Methoden, insbesondere in Szenarien, in denen andere Solver unter Instabilität oder Versagen litten.

Bedeutung und Behauptungen
Die Arbeit behauptet, dass ROR-BK eine vielversprechende Alternative für das Lösen linearer Systeme darstellt, bei denen die Matrix $A$ schlecht konditioniert ist, indem es effiziente Approximationen ohne die Notwendigkeit einer expliziten Präkonditionierung erreicht. Die Autoren argumentieren, dass Präkonditionierer zwar darauf abzielen, die Konditionszahl der Matrix zu reduzieren, dies jedoch nicht zwangsläufig die Konditionszahl des Problems selbst reduziert und Instabilitäten einführen kann. Durch die Partitionierung des Systems in Blöcke und die Nutzung von effektiver Orthogonalität und Regularisierung verteilt ROR-BK die kovarianten Gleichungen in potenziell gut konditionierte Teilprobleme.

Die Autoren positionieren die Methode als robusten Solver für quadratische, überbestimmte und unterbestimmte Systeme. Sie legen ferner nahe, dass ihr Nutzen als Pre-Solver oder innere Iteration zur Beschleunigung anderer iterativer Methoden wie GMRES besteht, insbesondere in Fällen, in denen Standard-Präkonditionierungstechniken aufgrund von Pivot-Breakdowns oder Rangdefizit versagen. Die Arbeit betont, dass die Kombination aus residuenbasierter Dynamik und Orthogonalitäts-Abtastung einen einfachen, aber effektiven Mechanismus für eine schnelle und stabile Konvergenz in Linearsystemen mit hoher Konditionszahl bietet.