Abstract
Transportation cost metrics, also known as the Wasserstein distances W_p, are a natural choice for defining distances between two pointsets, or distributions, and have been applied in numerous fields. From the computational perspective, there has been an intensive research effort for understanding the W_p metrics over R^k, with work on the W_1 metric (a.k.a earth mover distance) being most successful in terms of theoretical guarantees. However, the W_2 metric, also known as the rootmean square (RMS) bipartite matching distance, is often a more suitable choice in many application areas, e.g. in graphics. Yet, the geometry of this metric space is currently poorly understood, and efficient algorithms have been elusive. For example, there are no known nontrivial algorithms for nearestneighbor search or sketching for this metric.
In this paper we take the first step towards explaining the lack of efficient algorithms for the W_2 metric, even over the threedimensional Euclidean space R^3. We prove that there are no meaningful embeddings of W_2 over R^3 into a wide class of normed spaces, as well as that there are no efficient sketching algorithms for W_2 over R^3 achieving constant approximation. For example, our results imply that: 1) any embedding into L1 must incur a distortion of Omega(sqrt(log(n))) for pointsets of size n equipped with the W_2 metric; and 2) any sketching algorithm of size s must incur Omega(sqrt(log(n))/sqrt(s)) approximation. Our results follow from a more general statement, asserting that W_2 over R^3 contains the 1/2snowflake of all finite metric spaces with a uniformly bounded distortion. These are the first nonembeddability/nonsketchability results for W_2.
BibTeX  Entry
@InProceedings{andoni_et_al:LIPIcs:2016:6202,
author = {Alexandr Andoni and Assaf Naor and Ofer Neiman},
title = {{Impossibility of Sketching of the 3D Transportation Metric with Quadratic Cost}},
booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
pages = {83:183:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770132},
ISSN = {18688969},
year = {2016},
volume = {55},
editor = {Ioannis Chatzigiannakis and Michael Mitzenmacher and Yuval Rabani and Davide Sangiorgi},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6202},
URN = {urn:nbn:de:0030drops62028},
doi = {10.4230/LIPIcs.ICALP.2016.83},
annote = {Keywords: Transportation metric, embedding, snowflake, sketching}
}
Keywords: 

Transportation metric, embedding, snowflake, sketching 
Collection: 

43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) 
Issue Date: 

2016 
Date of publication: 

23.08.2016 