Better embeddings for planar Earth-Mover Distance over sparse sets

We consider the problem of constructing low-distortion embeddings of the Planar Earth-Mover Distance (EMD) into ℓp spaces. EMD is a popular measure of dis-similarity between sets of points, e.g., bags of geometric features. We present a collection of embeddings with the property that their distortion and/or host-space dimension are parametrized by the size (or the sparsity) of the embedded sets s. Our specific results include: • An O(log s)-distortion embedding of EMD over s-subsets into ℓ1−ϵ. This is the first embedding of EMD into a "tractable" ℓp space whose distortion is a function of the sparsity, not the size of the ambient space; • An O(log n)-distortion embedding of EMD into ℓ1 with dimension O(s2 log2 n), where the embedded sets are subsets of an n × n grid. For low values of s this significantly improves over the best previous dimension bound of O(n2) obtained for general sets.