ISBN 9783843951319

978-3-8439-5131-9, Reihe Mathematik

Frederic Matter
Sparse Recovery Under Side Constraints Using Null Space Properties

259 Seiten, Dissertation Technische Universität Darmstadt (2022), Softcover, B5

Zusammenfassung / Abstract

The problem of recovering a sparse vector via an underdetermined system of linear equations using a measurement matrix is one of the fundamental tasks in Compressed Sensing. In many applications, there is additional knowledge available, such as nonnegativity or integrality of the sparse vector, which can be exploited in the recovery problem. In order to characterize when recovery of sufficiently sparse vectors is possible, so-called Null Space Properties (NSPs) can be used.

In this thesis, a general framework for sparse recovery is presented, which allows to incorporate additional knowledge in form of side constraints and a general NSP is proposed, which subsumes many specific settings already considered in the literature. This framework allows to analyze the influence of side constraints on the recovery process. For several explicit settings and side constraints, specific NSPs are derived and compared. Moreover, the influence of nonnegativity in the case of sparse vectors is analyzed by considering whether random measurement matrices satisfy the corresponding NSPs. To complement this analysis, the problem of testing whether a given measurement matrix satisfies the respective NSP is formulated as a mixed-integer program for the explicit cases of sparse (nonnegative) vectors and block-sparse (nonnegative) vectors.

Lastly, new presolving and propagation techniques for general mixed-integer semidefinite programs (MISDPs) are developed, which allow for a significant improvement in the solution times, as a numerical evaluation on several classes of MISDPs reveals. In this computational study, a focus lies on the MISDP formulation of the Restricted Isometry Property (RIP), which is another recovery guarantee for sparse vectors.