K-Median Clustering, Model-Based Compressive Sensing, and Sparse Recovery for Earth Mover Distance

Details K-Median Clustering, Model-Based Compressive Sensing, and Sparse Recovery for Earth Mover Distance K-Median Clustering, Model-Based Compressive Sensing, and Sparse Recovery for Earth Mover Distance

2011-04-25

arxiv.org/abs/1104.4674v1

Computer Science

Data Structures and Algorithms

21 pages. Appearing in STOC 2011

Scientific paper

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 + epsilon approximation factor, which matches the best achievable bound for other error measures, such as the L_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.

Affiliated with

Also associated with

No associations

Rating

K-Median Clustering, Model-Based Compressive Sensing, and Sparse Recovery for Earth Mover Distance does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with K-Median Clustering, Model-Based Compressive Sensing, and Sparse Recovery for Earth Mover Distance, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and K-Median Clustering, Model-Based Compressive Sensing, and Sparse Recovery for Earth Mover Distance will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-544486