Weighted l$^{1}$-Analysis minimization and stochastic gradient descent for low rank matrix recovery

Fell, Jonathan Martin; Rauhut, Holger (Thesis advisor); Führ, Hartmut (Thesis advisor)

Aachen : RWTH Aachen University (2020, 2021)
Doktorarbeit

Dissertation, RWTH Aachen University, 2020

Kurzfassung

Diese Arbeit hat zwei Schwerpunkte: Zunächst werden die üblichen Methoden, die aus dem Bereich Compressed Sensing bekannt sind, erweitert. Der Grundgedanke dieser Methoden, bei denen ein unterbestimmtes lineares Gleichungssystem gelöst werden soll, ist stets, dass die Ursprungssignale, die rekonstruiert werden sollen, eine wesentlich niedrig dimensionalere Struktur besitzen als der Raum aus dem sie stammen. Dies wird üblicherweise dadurch zum Ausdruck gebracht, dass diese Signale dünnbesetzt sind, also wenige signifikante Koeffizienten in einer Basis des zugrundeliegenden Vektorraumes haben. Im ersten Teil dieser Arbeit wird dieser Begriff der Dünnbesetztheit nun dahingehend erweitert, dass vermöge Gewichten bestimmte Anteile der Ursprungsdaten stärker betont werden als andere. Insbesondere wird ein Algorithmus entwickelt der es ermöglicht, ebensolche Signale aus unterbestimmten linearen Messungen wiederzugewinnen. Im anschließenden Kapitel wird dieser Gedanke weiterverfolgt und ausgebaut, indem anstatt faktischer Dünnbesetztheit in einer Vektorraumbasis die Signale in einem weitaus allgemeineren Repräsentationssystem wenige signifikante Koeffizienten haben sollen. Diese Systeme sind hier sogenannte Frames, redundante Erzeugendensysteme von Vektorräumen, die es erlauben, bestimmte Klassen von Signalen anhand des Abklingverhaltens der Framekoeffizienten von Signalen zu charakterisieren. Dies kombinieren wir mit der Gewichtung aus dem ersten Teil der Arbeit, mit dem Ziel die Resultate auf unendlich dimensionale Vektorräume zu erweitern. Der zweite Hauptaspekt dieser Dissertation ist die Rekonstruktion von Niedrigrangmatrizen aus quadratischen Messungen, die zusätzlich blind gegenüber orthogonalen Transformationen sind. Die Annahme, dass die ursprünglichen Matrizen niedrigen Rang haben ist hier das Analog zur Dünnbesetztheit bei Vektoren. Es wird ein Algorithmus entwickelt und vorgestellt, der diese Matrizen bis auf eine orthogonale Transformation rekonstruiert. Die Tatsache, dass die Messungen in diesem Falle quadratisch und nicht mehr linear sind, wie in den vorigen Kapiteln, stellt eine zusätzliche Herausforderung dar. Bei allen vorgestellten Resultaten liegt ein Hauptaugenmerk auf der Größe der zu lösenden Gleichungssysteme, das heißt dem Verhältnis der benötigen Messungen zur Dimension des zugrundeliegenden Signalraumes. Weiterhin werden stets numerische Beispiele vorgestellt, um die praktische Anwendbarkeit der entwickelten Methoden vorzuführen. Insbesondere für den ersten Teil, der Signalrekonstruktion anhand gewichteter Koeffizienten in redundanten Systemen, der gewichteten Framekoeffizienten-Minimierung, werden die algorithmischen Methoden auf Messungen aus Computertomographen angewandt, womit gezeigt werden kann, dass dieser Ansatz auch Vorteile in der Anwendung auf reale Daten hat.

Einrichtungen

• Fachgruppe Mathematik [110000]
• Lehrstuhl für Mathematik der Informationsverarbeitung [114510]