CS: Model-Based Compressive Sensing

Woohoo. If you recall, Model-based compressive sensing is a way of acquiring less compressive sensing signals than usual by using the tree-like structure of images in wavelet bases. The authors at Rice Richard Baraniuk, Volkan Cevher, Marco Duarte, Chinmay Hegde, Michael Wakin have written the following papers on it (Preprint, SPARS 2009, CISS 2009, NIPS 2008, ICASSP 2008, SPARS 2005). They have released the attendant toolbox. From the website:

The standard compressive sensing (CS) theory dictates that robust signal recovery is possible from $M=O(K\log(N/K))$ measurements. We demonstrate that it is possible to substantially decrease $M$ without sacrificing robustness by leveraging more realistic signal models that go beyond simple sparsity and compressibility by including dependencies between values and locations of the signal coefficients.

We have designed algorithms that enable fast recovery of piecewise smooth signals - sparse signals that have a distinct "connected tree" structure in the wavelet domain. Our Tree Matching Pursuit (TMP) algorithm significantly reduces the search space of the traditional Matching Pursuit greedy algorithm, resulting in a substantial decrease in computational complexity for recovering piecewise smooth signals. Our Hidden Markov Tree-based Reweighted $\ell_1$-norm minimization algorithm leverages the probabilistic model for wavelet-sparse signals to enable a reduction on the number of measurements necessary for recovery. An additional advantage of these algorithms is that they perform an implicit regularization to combat noise in the reconstruction.

We also propose a union-of-subspaces model-based CS theory that parallels the conventional theory and provides concrete guidelines on how to create model-based recovery algorithms with provable performance guarantees. For some well-suited signal models, we can provably offer robust recovery from just $M=O(K)$ measurements.