Title: Impossibility of Sketching of the 3D Transportation Metric with Quadratic Cost

Author: Alex Andoni, Assaf Naor and Ofer Neiman 

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 {\em earth mover
  distance}) being most successful in terms of theoretical
guarantees. However, the $\W_2$ metric, also known as the {\em
  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 $\W_2$ metric, even over the
three-dimensional 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 $L_1$ 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\left(\sqrt{\log n}/\sqrt{s}\right)$
approximation. Our results follow from a more general statement,
asserting that $\W_2$ over $\R^3$ contains the 1/2-snowflake of {\em
  all} finite metric spaces with a uniformly bounded distortion. These
are the first non-embeddability/non-sketchability results for $\W_2$.