Impossibility of sketching of the 3D transportation metric with quadratic cost

Alexandr Andoni, Assaf Naor, Ofer Neiman

Research output: Chapter in Book/Report/Conference proceedingConference contribution

7 Scopus citations

Abstract

Transportation cost metrics, also known as the Wasserstein distances Wp, 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 Wp metrics over Rk, with work on the W1 metric (a.k.a earth mover distance) being most successful in terms of theoretical guarantees. However, the W2 metric, also known as the root-mean 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 non-trivial algorithms for nearest-neighbor search or sketching for this metric. In this paper we take the first step towards explaining the lack of efficient algorithms for the W2 metric, even over the three-dimensional Euclidean space R3. We prove that there are no meaningful embeddings of W2 over R3 into a wide class of normed spaces, as well as that there are no efficient sketching algorithms for W2 over R3 achieving constant approximation. For example, our results imply that: 1) any embedding into L1 must incur a distortion of Ω(√log n) for pointsets of size n equipped with the W2 metric; and 2) any sketching algorithm of size s must incur Ω(√log n/√s) approximation. Our results follow from a more general statement, asserting that W2 over R3 contains the 1/2-snowflake of all finite metric spaces with a uniformly bounded distortion. These are the first non-embeddability/non-sketchability results for W2.

Original languageEnglish (US)
Title of host publication43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016
EditorsYuval Rabani, Ioannis Chatzigiannakis, Davide Sangiorgi, Michael Mitzenmacher
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770132
DOIs
StatePublished - Aug 1 2016
Event43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016 - Rome, Italy
Duration: Jul 12 2016Jul 15 2016

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume55
ISSN (Print)1868-8969

Other

Other43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016
CountryItaly
CityRome
Period7/12/167/15/16

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Embedding
  • Sketching
  • Snowflake
  • Transportation metric

Fingerprint Dive into the research topics of 'Impossibility of sketching of the 3D transportation metric with quadratic cost'. Together they form a unique fingerprint.

Cite this