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)
Dissertation / PhD Thesis

Dissertation, RWTH Aachen University, 2020

Abstract

This dissertation focuses on two topics: First of all, two extensions to the usual approach of Compressed Sensing are discussed. Compressed Sensing aims at solving an underdetermined linear equation by exploiting the assumption that the original signal comes from a low-complexity class if signals. Usually, this is expressed by the notion of sparsity, that is to say that the signals only possess few significant coefficients in a basis of the underlying vector space. The first part of this dissertation extends the notion of sparsity by employing additional weights to emphasize certain parts of the signal. An algorithm is developed that allows for the reconstruction of such a signal from an underdetermined linear equation by using those weights. In the following chapter, the idea of extending prior methods is persevered and extended in such a way as the sparsity of the signal in a basis of the vector space is exchanged for sparsity in a more general representation system. These systems are, for this work, so-called frames, redundant generating systems of vector spaces that allow for the characterization of certain classes of signals by the decay of the frame coefficients of these signals. This is combined with the weighting process from the first part of this work to extend these results to infinite dimensional vector spaces. The second main aspect of this dissertation is the reconstruction of low-rank matrices from quadratic measurements which are moreover oblivious to orthogonal transformations. The low-rank assumption is the matrix analog of sparsity in the case of the reconstruction of vectorized signals. An algorithm is developed and presented that reconstructs the original matrix up to a global orthogonal transformation. The fact that the measurements are quadratic instead of linear, as they were in the former chapters, is and additional challenge to the analysis. One main focus of all the results that are going to be presented is the size of the equation systems, i.e., the ration of the number of measurements needed to ensure approximation or reconstruction and the dimension of the underlying vector space. Moreover, numerical examples will be presented to demonstrate the applicability of the methods that were developed here. Especially in the first part, the weighted minimization of analysis coefficients, the algorithms that were developed will be applied to real-world data from Computer Tomography to show that this approach can be beneficial for the application to real-world data.

Institutions

• Department of Mathematics [110000]
• Chair of Mathematics of Information Processing [114510]