Compressed sensing has brought the use of sparsity- and compressibility-based signal models to the forefront of data acquisition. The well-known analyses of compressed sensing are indirect and hold pointwise over the possible signals of interest. Inspired by the extreme conservatism of these analyses, we develop a Bayesian analysis using the replica method. This gives asymptotically-exact performance analyses for a large class of estimators applied to a large class of problems. In particular, it shows that lasso typically performs much better than predicted by previous analyses.

Bayesian formulations are amenable to new generalized approximate message passing (GAMP) algorithms. We develop a GAMP algorithm for estimation from quantized samples, which arise in analog-to-digital conversion and compression. The GAMP algorithm provides large improvements over conventional reconstruction. The state evolution formalism of GAMP enables efficient optimization of quantizers, leading to further improvement.

The talk is based on joint work with Alyson Fletcher, Ulugbek Kamilov, and Sundeep Rangan.