MADALGO seminar: Ludwig Schmidt, Massachusetts Institute of Technology (MIT) - The Constrained Earth Mover Distance Model with Applications to Compressive Sensing

Abstract:

Sparse signal representations have emerged as powerful tools in signal processing theory and applications, and serve as the basis of the now-popular field of compressive sensing (CS). However, several practical signal ensembles exhibit additional, richer structure beyond mere sparsity. Our particular focus in this talk is on signals and images where, owing to physical constraints, the positions of the nonzero coefficients do not change significantly as a function of spatial (or temporal) location. Such signal and image classes are often encountered in seismic exploration, astronomical sensing, and biological imaging.

Our contributions are threefold: (i) We propose a simple, deterministic model based on the Earth Mover Distance that effectively captures the structure of the sparse nonzeros of signals belonging to such classes. (ii) We formulate an approach for approximating any arbitrary signal by a signal belonging to our model. The key idea in our approach is a min-cost max-flow graph optimization problem that can be solved efficiently. (iii) We develop a CS algorithm for efficiently reconstructing signals belonging to our model, and numerically demonstrate its benefits over state-of-the-art CS approaches.

Joint work with: Chinmay Hegde and Piotr Indyk

Host: Lars Arge