Better embeddings for Planar Earth-Mover Distance oversparse sets; Better embeddings for Planar EMD over sparsesets
Artūrs Bačkurs · 2014
We consider the problem of constructing low-distortion embeddings of the Planar Earth-Mover Distance (EMD) into lp spaces. EMD is a popular measure of dissimilarity 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 l1-e. This is the first embedding of EMD into a tractable lp, 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 lp, with dimension O(s2 log2 n), where the embedded sets are subsets of an n x n grid. For low values of s this significantly improves over the best previous dimension bound of 0(n 2 ) obtained for general sets.