An important problem in statistics, machine learning, and modern signal processing is to recover information of limited complexity, or, more specifically, of low-dimensional structure, from seemingly few data.
Often, this amounts to recover a sparse signal, i.e., a signal which is non-zero at few locations only, by solving an under-determined system of linear equations. In this thesis, we will use ideas from sparse signal recovery to cluster high dimensional data points, to identify sparse linear operators, and to recover sparse signals with certain block-structure.