Toward Theoretically Founded Learning-Based Compressed Sensing

© 1963-2012 IEEE. Noiseless compressed sensing refers to the problem of recovering a (high-dimensional) signal from its under-determined linear measurements. For compressed sensing to be feasible, the signal needs to be structured. While the main focus of the field has been on simple structures such as sparsity, there has been a growing interest in moving beyond sparsity and having a comprehensive compressed sensing framework that covers general structures. Two recent approaches that aim at developing such a framework from different perspectives are i) Quantized maximum a posteriori (Q-MAP), a Bayesian method that assumes full knowledge of the source distribution, and ii) Lagrangian minimum entropy pursuit (L-MEP), a universal recovery method that requires no prior knowledge about the distribution of the source. In this paper, by establishing theoretical connections between L-MEP and Q-MAP, it is shown how the two methods are complementary to each other and lead to a theoretically-founded learning-based recovery method that applies to sources with general structures. Unlike a Bayesian or a universal method, a learning-based method is able to extract the source structure from training data. The effect of error in estimating the source structure on the performance of the learning-based compressed sensing recovery method is characterized.