Department Colloquium: Vivek Goyal

Abstract:

Compressed sensing has brought the use of sparsity- and compressibility-based signal models to the forefront of data acquisition and inverse problems.  The well-known analyses of compressed sensing are indirect and hold pointwise over the possible signals of interest. Inspired by the conservatism of these analyses, we developed a Bayesian analysis framework.  Under the assumption of replica symmetry, we prove convergence in distribution as problem size grows of the joint marginal of one variable of interest and its estimate to the joint distribution in a simple scalar equivalent problem.  This gives a simple mechanism for asymptotically-exact performance computations that applies to a large class of estimators applied to a large class of problems.  For example, it shows that l1-regularized least squares estimation typically performs much better than predicted by previous analyses.

I will show a connection between the replica-symmetric analysis and approximate message passing (AMP) algorithms.  Bayesian formulations are also amenable to new message passing algorithms for many inverse problems.  A generalized AMP algorithm applied to estimation problems with quantized samples provides large improvements over previous methods.  Hybrid generalized AMP allows a flexible trade-off between computational complexity and fidelity to conventional belief propagation.  Its efficacy on a problem with group sparse structure is demonstrated.