Computational Aspects of Compressed Sensing

Andreas Tillmann
Doctoral Dissertation

A central task in the novel field of Compressed Sensing is sparse recovery, i.e., finding the sparsest exact or approximate solution to an underdetermined linear equation system. Over the past decade, several conditions have been identified under which this generally intractable problem can be solved efficiently.

In this thesis, we investigate the computational complexity of ubiquitous sparse recovery conditions based on the spark, the restricted isometry property and the nullspace property of the sensing matrix. Furthermore, we provide an extensive numerical comparison of various state-of-the-art solvers for the most popular sparse recovery approach, the Basis Pursuit (L1-norm minimization) model, and demonstrate how a novel heuristic optimality check can significantly improve both speed and accuracy of most solvers. In addition, we introduce a new subgradient algorithm involving adaptive approximate projections for general nonsmooth convex constrained optimization and discuss its application to Basis Pursuit and variants.

» Show BibTeX

author = {A. M. Tillmann},
title = {{Computational Aspects of Compressed Sensing}},
howpublished = {Doctoral Dissertation},
school = {TU Darmstadt, Germany},
year = {2013}

Disclaimer Home Visual Computing institute RWTH Aachen University