## 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 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 Ω(√log n) for pointsets of size n equipped with the W_{2} 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 W_{2} over R^{3} 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 W_{2}.

Original language | English (US) |
---|---|

Title of host publication | 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016 |

Editors | Yuval Rabani, Ioannis Chatzigiannakis, Davide Sangiorgi, Michael Mitzenmacher |

Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |

ISBN (Electronic) | 9783959770132 |

DOIs | |

State | Published - Aug 1 2016 |

Event | 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016 - Rome, Italy Duration: Jul 12 2016 → Jul 15 2016 |

### Publication series

Name | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|

Volume | 55 |

ISSN (Print) | 1868-8969 |

### Other

Other | 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016 |
---|---|

Country | Italy |

City | Rome |

Period | 7/12/16 → 7/15/16 |

## All Science Journal Classification (ASJC) codes

- Software

## Keywords

- Embedding
- Sketching
- Snowflake
- Transportation metric