Inexact Douglas–Rachford iterations for variants of total generalized variation denoising in mathematical imaging

Vestweber, Lena

doi:10.24355/dbbs.084-202201071209-0

Published

Inexact Douglas–Rachford iterations for variants of total generalized variation denoising in mathematical imaging

English
German

Diﬀerent (in some sense equivalent) versions of the total generalized variation (TGV) denoising method [4] are proposed, which have several advantages over the classical one: First, working with constraints in contrast to penalties, in some cases, allows for a simple, clean and eﬀective parameter choice. The resulting method is a so-called Morozov type formulation of the TGV problem and therefore referred to as MTGV. Second, a variable change in these problems leads to diﬀerent dual problems and hence, diﬀerent algorithms and some of these turn out to be simpler regarding duality gaps and stopping. The Douglas–Rachford method is used to solve these minimization problems. This involves the solution of large discretizations of linear partial diﬀerential equations in each
step of the Douglas–Rachford method and simple and eﬀective preconditioners are developed for these equations. In contrast to [7] where the authors use classical linear splitting methods for the inexact solution of the linear equations, in this thesis it is proposed to
use a few iterations of the preconditioned conjugate gradient method. The linear operators are discretizations of continuous diﬀerential operators. Hence the resolvent steps in the Douglas–Rachford iteration correspond to solutions of certain diﬀerential equations. In this context it has been shown to be beneficial to motivate preconditioners for the linear systems by their continuous counterparts, see [24]. Block diagonal preconditioners turn out to be a natural choice for these operators. Experiments are made with the
TGV and MTGV problem with and without variable change, where the inexact Douglas–Rachford algorithm and the Chambolle–Pock method are used. The TGV and MTGV method are comparable with both algorithms considering computational time when the images were corrupted with a high level of noise. For low noise levels the Chambolle–Pock algorithm was faster than the Douglas–Rachford algorithm. The variable change leads to much slower algorithms, but it motivates a modified duality gap that can also be used as a stopping criterion for the original problem. Finally, the step sizes of the Douglas–Rachford algorithm are analyzed. A rescaling of the TGV denoising method leads to a second step size in the Douglas–Rachford algorithm, which can be chosen independently of the first one (see [26]). It seems to be common knowledge that there is a sweet spot for
these step sizes to obtain optimal convergence properties. There exist rules for choosing the step sizes in some special cases. In the general case the step sizes are often obtained by trial and error. In this thesis, rules for the step sizes for some linear Douglas–Rachford operators are derived by analyzing their eigenstructure.

In dieser Arbeit werden verschiedene Versionen der TGV (total generalized variation) Entrauschmethode [4] untersucht, die einige Vorteile gegenüber der klassischen Methode haben: Indem man mit Nebenbedingungen anstatt Straftermen arbeitet, erhält man in einigen Fällen eine einfache automatische Parameterwahl. Die resultierende Methode ist eine Morozov Regularisierung und wird deswegen MTGV genannt. Desweiteren wird ein Variablenwechsel untersucht. Dieser führt sowohl bei TGV als auch bei MTGV zu veränderten dualen Problemen und damit zu veränderten Algorithmen. Es stellt sich heraus, dass diese eine einfacher nutzbare Dualitätslücke haben, die bei klassischen Algorithmen wie Douglas–Rachford und Chambolle–Pock endlich ist und damit als Abbruchkriterium verwendet werden kann. In dieser Arbeit wird die Douglas–Rachford Methode zur Lösung oben genannter Minimierungsprobleme verwendet. In jedem Iterationsschritt der Douglas–Rachford Methode muss ein großes lineares Gleichungssystem gelöst werden, welches der Diskretisierung einer partiellen Diﬀerentialgleichung entspricht. Hierführ werden geeignete Präkonditionierer entwickelt. Im Unterschied zu [7], wo die Autoren wenige Schritte von klassischen linearen Splitting-Verfahren für die inexakte Lösung des linearen Gleichungssystems verwenden, wird in dieser Arbeit empfohlen, wenige Schritte des präkonditionierten CG Verfahrens zu verwenden. Die linearen Operatoren entsprechen Diskretisierungen von kontinuierlichen Diﬀerentialoperatoren. Damit entsprechen die Auswertungen der Resolventen in der Douglas–Rachford Methode dem Lösen von Diﬀerentialgleichungen. In diesem Kontext hat es sich als nützlich erwiesen, Präkonditionierer für die linearen Gleichungssysteme durch deren kontinuierliche Entsprechungen auf unendlichdimensionalen Räumen zu motivieren, siehe [24]. Dabei stellt sich heraus, dass blockdiagonale Operatoren in gewissem Sinne eine natürliche Wahl für diese Operatoren darstellen. Experimente werden durchgeführt mit dem TGV und dem MTGV Entrauschproblem mit und ohne Variablenwechsel, wobei der Douglas–Rachford Algorithmus und der Chambolle–Pock Algorithmus verwendet werden. Dabei sind TGV und MTGV vergleichbar bei beiden Algorithmen bezüglich der Rechenzeit bei starkem Rauschen. Bei schwachem Rauschen liefert der Chambolle–Pock Algorithmus bessere Ergebnisse. Der Variablenwechsel führt zu deutlich langsameren Algorithmen. Dennoch motivierte der Variablenwechsel ein Abbruchkriterium, das auch für die Originalprobleme verwendet werden kann. Schließlich werden die Schrittweiten des Douglas–Rachford Verfahrens untersucht. Eine Reskalierung des TGV Problems führt zu einer zweiten Schrittweite im Douglas–Rachford Algorithmus, die unabhängig von der ersten gewählt werden kann, siehe [26]. Es scheint allgemein bekannt zu sein, dass es einen optimalen Bereich für diese Schrittweiten gibt. Im Allgemeinen werden diese Schrittweiten aber oft durch Versuch und Irrtum bestimmt. In dieser Arbeit werden optimale Schrittweiten für einfache lineare Douglas–Rachford Operatoren hergeleitet, indem deren Eigenstruktur untersucht wird.