K-median clustering, model-based compressive sensing, and sparse recovery for earth mover distance
We initiate the study of sparse recovery problems under the Earth-Mover Distance (EMD). Specifically, we design a distribution over m x n matrices A such that for any x, given Ax, we can recover a k-sparse approximation to x under the EMD distance. One construction yields m=O(k log (n/k)) and a 1 +...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Association for Computing Machinery (ACM)
2012
|
| Online Access: | http://hdl.handle.net/1721.1/73011 https://orcid.org/0000-0002-7983-9524 |
| _version_ | 1826211407498051584 |
|---|---|
| author | Indyk, Piotr Price, Eric C. |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Indyk, Piotr Price, Eric C. |
| author_sort | Indyk, Piotr |
| collection | MIT |
| description | We initiate the study of sparse recovery problems under the Earth-Mover Distance (EMD). Specifically, we design a distribution over m x n matrices A such that for any x, given Ax, we can recover a k-sparse approximation to x under the EMD distance. One construction yields m=O(k log (n/k)) and a 1 + ε approximation factor, which matches the best achievable bound for other error measures, such as the l[subscript 1] norm.
Our algorithms are obtained by exploiting novel connections to other problems and areas, such as streaming algorithms for k-median clustering and model-based compressive sensing. We also provide novel algorithms and results for the latter problems. |
| first_indexed | 2024-09-23T15:05:24Z |
| format | Article |
| id | mit-1721.1/73011 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T15:05:24Z |
| publishDate | 2012 |
| publisher | Association for Computing Machinery (ACM) |
| record_format | dspace |
| spelling | mit-1721.1/730112022-09-29T12:37:30Z K-median clustering, model-based compressive sensing, and sparse recovery for earth mover distance Indyk, Piotr Price, Eric C. Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Indyk, Piotr Indyk, Piotr Price, Eric C. We initiate the study of sparse recovery problems under the Earth-Mover Distance (EMD). Specifically, we design a distribution over m x n matrices A such that for any x, given Ax, we can recover a k-sparse approximation to x under the EMD distance. One construction yields m=O(k log (n/k)) and a 1 + ε approximation factor, which matches the best achievable bound for other error measures, such as the l[subscript 1] norm. Our algorithms are obtained by exploiting novel connections to other problems and areas, such as streaming algorithms for k-median clustering and model-based compressive sensing. We also provide novel algorithms and results for the latter problems. 2012-09-17T17:53:06Z 2012-09-17T17:53:06Z 2011-06 Article http://purl.org/eprint/type/ConferencePaper 978-1-4503-0691-1 http://hdl.handle.net/1721.1/73011 Piotr Indyk and Eric Price. 2011. K-median clustering, model-based compressive sensing, and sparse recovery for earth mover distance. In Proceedings of the 43rd annual ACM symposium on Theory of computing (STOC '11). ACM, New York, NY, USA, 627-636. https://orcid.org/0000-0002-7983-9524 en_US http://dx.doi.org/10.1145/1993636.1993720 Proceedings of the 43rd annual ACM symposium on Theory of computing (STOC '11) Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Association for Computing Machinery (ACM) MIT web domain |
| spellingShingle | Indyk, Piotr Price, Eric C. K-median clustering, model-based compressive sensing, and sparse recovery for earth mover distance |
| title | K-median clustering, model-based compressive sensing, and sparse recovery for earth mover distance |
| title_full | K-median clustering, model-based compressive sensing, and sparse recovery for earth mover distance |
| title_fullStr | K-median clustering, model-based compressive sensing, and sparse recovery for earth mover distance |
| title_full_unstemmed | K-median clustering, model-based compressive sensing, and sparse recovery for earth mover distance |
| title_short | K-median clustering, model-based compressive sensing, and sparse recovery for earth mover distance |
| title_sort | k median clustering model based compressive sensing and sparse recovery for earth mover distance |
| url | http://hdl.handle.net/1721.1/73011 https://orcid.org/0000-0002-7983-9524 |
| work_keys_str_mv | AT indykpiotr kmedianclusteringmodelbasedcompressivesensingandsparserecoveryforearthmoverdistance AT priceericc kmedianclusteringmodelbasedcompressivesensingandsparserecoveryforearthmoverdistance |