Speaker:  Dr. Chinmay Hegde

Abstract:
Compressive Sensing (CS) stipulates that a sparse signal can be exactly recovered from a small number of linear measurements, and that this recovery can be performed efficiently in polynomial time. However, several practical signals exhibit additional structure beyond mere sparsity. The framework of model-based compressive sensing (model-CS) leverages this additional structure and prescribes new recovery schemes that can reduce the number of measurements even further. This idea has led to measurement-efficient recovery schemes for a variety of signal models, including block-sparse signals, tree-sparse signals, and separated spikes.

However, for any given model, the viability of model-CS requires the availability of an algorithm for the following optimization task (referred to as "model-projection"): given an arbitrary signal x, produce the closest signal to x that lies in the model. Often, this optimization can be computationally very expensive and for some models, even NP-hard. Further, an approximation algorithm for this optimization task is insufficient. This requirement poses a fundamental obstacle for extending model-CS to an even richer class of problems. In this talk, we remove this obstacle and show how to extend model-CS so that it requires only approximate model-projection. Interestingly, our new approach requires approximation algorithms to both the minimization- and maximization-variants of the model-projection problem.

We instantiate this new framework for a new signal model that we call the Constrained Earth Mover Distance (CEMD) model. This model is particularly useful for signal ensembles where the positions of the nonzero coefficients do not change significantly as a function of spatial (or temporal) location. Such ensembles are often encountered in seismic exploration, surveillance, and astronomical sensing. We develop approximation algorithms for model-projection via graph optimization techniques; leverage these algorithms into efficient model-CS recovery techniques; and numerically demonstrate its benefits over the state-of-the-art.

Bio:
Chinmay Hegde received the B.Tech. degree in 2006 in electrical engineering from IIT Madras (India), and M.S. and Ph.D. degrees in electrical and computer engineering from Rice University, Houston, TX, in 2010 and 2012, respectively. He joined the Theory of Computation (TOC) Group at MIT in October 2012, where he is currently a Shell-MIT postdoctoral research associate. His research interests include statistical signal processing and machine learning.