Abstract
Compressive sensing investigates the recovery of a signal that can be sparsely represented in an orthonormal basis or overcomplete dictionary given a small number of linear combinations of the signal. We present a novel matching pursuit algorithm that uses the measurements to probabilistically select a subset of bases that is likely to contain the true bases constituting the signal. The algorithm is successful in recovering the original signal in cases where deterministic matching pursuit algorithms fail. We also show that exact recovery is possible when the number of nonzero coefficients is upto one less than the number of measurements. This overturns a previously held assumption in compressive sensing research.
Date of this Version
5-6-2010