The Bregman-Kaczmarz Method : Inconsistency, Acceleration and Nonlinearity
The Bregman-Kaczmarz method, originally “sparse“ Kaczmarz method, is a randomized iterative algorithm which can solve strongly convex problems subject to a constraint given by a linear system and uses only one or a selected number of rows of the involved matrix in each iteration. Such methods are interesting for large-scale systems, which for instance arise in the reconstruction problem of computerized tomography, or if computational units admit limited random access memory. The objective function can be chosen to find solutions with only a few nonzero entries, so-called sparse solutions, which explains the original name. This thesis treats different kinds of extensions of the method. First, we propose additional steps in case that the linear system has no solution. Our algorithm successively projects the right-hand side onto the image of the system matrix by using one or several columns, and solves the original optimization problem with respect to this new right-hand side. Here, the projection is with respect to a convex distance, which can be chosen according to the residual noise. In particular, the method can find sparse solutions of linear least squares problems, as well as sparse solutions of a system with respect to a right-hand side obtained by removing impulsive noise. As a second extension of the Bregman-Kaczmarz method, we propose two accelerations of “heavy ball“ kind. These methods rely on a principle which we call “minimal errors“. In the first case, the momentum parameter is chosen adaptively in such a way that it minimizes a Bregman distance, a special convex distance, to the exact solution, where this exact solution does not need to be known beforehand. In the second case, we minimize an upper bound for the Bregman distance, which leads to a quadratic minimization problem that is explicitly solvable and yields both an adaptive momentum parameter and an adaptive step size. As a result, we give convergence rates which improve on the known ones for constant choices of the momentum parameter. Acceleration is observed, among others, for an academic example of computerized tomography. As a third contribution, we extend the Bregman-Kaczmarz iterations to nonlinear systems subject to certain simple convex constraints. We prove convergence for convex nonnegative functions and functions which fulfill the so-called local tangential cone condition, an assumption frequently made in the literature of inverse problems to study first-order methods.
Das Bregman-Kaczmarz-Verfahren, ursprünglich „Sparse“-Kaczmarz-Verfahren, ist ein randomisierter iterativer Algorithmus, der stark konvexe Probleme unter linearen Nebenbedingungen löst und dabei in jedem Schritt nur eine oder eine ausgewählte Anzahl an Zeilen der beteiligten Matrix verwendet. Verfahren dieser Art sind für große lineare Systeme interessant, wie sie beispielsweise bei der Rekonstruktionsaufgabe der Computertomographie auftreten, oder wenn wenig Arbeitsspeicher für Rechnungen zur Verfügung steht. Die Zielfunktion kann so gewählt werden, dass Lösungen mit vielen Nulleinträgen, sogenannte dünnbesetzte (engl.: sparse) Lösungen, gefunden werden, was den ursprünglichen Namen des Algorithmus erklärt. In dieser Arbeit werden drei verschiedene Erweiterungen des Verfahrens entwickelt. Als ersten Beitrag führen wir zusätzliche Schritte für den Fall ein, dass die Nebenbedingung nicht lösbar ist. Unser Algorithmus projiziert dabei die rechte Seite sukzessive auf das Bild der Systemmatrix, was unter Hinzunahme einer oder mehrerer Spalten geschieht, und löst im Grenzwert das Ausgangsproblem mit dieser neuen rechten Seite. Die Projektion erfolgt hierbei bezüglich einer konvexen Distanz, die passend zur Art des Rauschens im Residuum gewählt werden kann. Insbesondere kann das Verfahren dünnbesetzte kleinste-Quadrate-Lösungen finden, sowie dünnbesetzte Lösungen mit einer rechten Seite, die durch Entfernen von Impulsrauschen gewonnen wird. Als zweite Erweiterung des Bregman-Kaczmarz-Verfahrens schlagen wir zwei Beschleunigungen vom Typ „Heavy Ball“ vor. Diese Verfahren beruhen auf einem Prinzip, das wir minimal error nennen. Im ersten Fall wird in jedem Schritt der Momentum-Parameter adaptiv gewählt, sodass die sogenannte Bregman-Distanz, eine spezielle konvexe Distanz, zur exakten Lösung minimiert wird, ohne dass diese Lösung im Vorhinein bekannt sein muss. Im zweiten Fall minimieren wir eine obere Schranke für die Bregman-Distanz, die zu einer quadratischen und somit analytisch lösbaren Minimierungsaufgabe führt und sowohl einen adaptiven Momentum-Parameter als auch eine adaptive Schrittweite liefert. Als Ergebnis beweisen wir verbesserte Konvergenzraten gegenüber denen, die für feste Wahlen des Momentum-Parameters bekannt sind. In numerischen Beispielen beobachten wir Beschleunigung, unter anderem für ein akademisches Beispiel aus der Computertomographie. Als dritten Beitrag weiten wir das Bregman-Kaczmarz-Verfahren auf nichtlineare Gleichungssysteme mit gewissen einfachen konvexen Nebenbedingungen aus. Wir beweisen Konvergenz für konvexe nichtnegative Funktionen sowie Funktionen, die die sogenannte lokale Tangentialkegelbedingung erfüllen, welche in der Inverse-Probleme-Literatur oft gefordert wird, um Verfahren erster Ordnung zu untersuchen.
Preview
Cite
Access Statistic
Rights
Use and reproduction:
