Model-based compressive sensing
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.
Authors: Richard G. Baraniuk, Volkan Cevher, Marco F. Duarte, Chinmay Hegde, Michael B. Wakin
Publications: Preprint, SPARS 2009, CISS 2009, NIPS 2008, ICASSP 2008, SPARS 2005
Software: ld-research-image-imceimage-path">
Related research at Rice