Better embeddings for planar Earth-Mover Distance over sparse sets
Artūrs Bačkurs, Piotr Indyk · 2014
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: