emd_flow : The Constrained Earth Mover Distance Model,with Applications to Compressive Sensing

Here is an extension of the Earth Mover's distance work that allows one to use a different kind of structured sparsity. Here it might even be very an extension of the generic MMV approach. 

The Constrained Earth Mover Distance Model,with Applications to Compressive Sensing by Ludwig Schmidt, Chinmay Hegde, Piotr Indyk. 

Abstract—Sparse signal representations have emerged as powerful tools in signal processing theory and applications, and serveas 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 inthis paper is on signals and images where, owing to physicalconstraints, the positions of the nonzero coefficients do not changesignificantly as a function of spatial (or temporal) location.Such signal and image classes are often encountered in seismicexploration, astronomical sensing, and biological imaging. Ourcontributions are threefold: (i) We propose a simple, deterministicmodel based on the Earth Mover Distance that effectively capturesthe structure of the sparse nonzeros of signals belonging to suchclasses. (ii) We formulate an approach for approximating anyarbitrary signal by a signal belonging to our model. The ke yidea in our approach is a min-cost max-flow graph optimization problem that can be solved efficiently in polynomial time. (iii)We develop a CS algorithm for efficiently reconstructing signalsbelonging to our model, and numerically demonstrate its benefitsover state-of-the-art CS approaches.

The attendant code for emd_flow is on Ludwig Schmidt's code page.

Other relevant papers:

• Automatic Fault Localization Using the Generalized Earth Mover's Distance
• Approximation-Tolerant Model-Based Compressive Sensing
• Automatic Fault Localization Using the Generalized Earth Mover's Distance
• Ludwig Schmidt's thesis: Model-Based Compressive Sensing with Earth Mover’s Distance Constraints

and eventually:

• Learning Manifolds in the Wild
• Around the blogs in 80 summer hours (NIPS and more)
• SAHD: Multiscale bi-Harmonic Analysis of Digital Data Bases and Earth moving distances - Raphy Coifman

Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.