Sparse recovery for Earth Mover Distance

Rishi Gupta, Piotr Indyk, Eric PriceAllerton 2010 · OpenReview

Abstract

We initiate the study of sparse recovery problems under the Earth-Mover Distance (EMD). Specifically, we design a distribution over m × n matrices A, for m ≪ n, such that for any x, given Ax, we can recover a k-sparse approximation to x under the EMD distance. We also provide an empirical evaluation of the method that show, in some scenarios, its advantages over the “usual” recovery in the ℓp norms.
BibTeX
@inproceedings{gupta2010sparse,
  author = {Rishi Gupta and Piotr Indyk and Eric Price},
  title = {{Sparse recovery for Earth Mover Distance}},
  booktitle = {Allerton},
  year = {2010},
  url = {https://openreview.net/forum?id=Ygr99HR8tK},
}

Loading related content...

Figure