Cross validation for compressive sensing

The compressive sensing framework aims to recover a sparse signal from a small set of projections onto incoherent vectors; the problem reduces to searching for a sparse approximation of the measurements obtained in an appropriate dictionary. Conventional solutions involve linear programming or greedy algorithms and can be computationally expensive. These techniques are generic, however, and assume no structure in the signal aside from sparsity. 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.

Authors: Richard G. Baraniuk, Petros T. Boufounos, Marco F. Duarte

Publications: SSP 2007

Related research at Rice