Thursday, May 08, 2014

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. 

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:
and eventually:

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.

No comments: