TY - JOUR

T1 - Snowflake universality of Wasserstein spaces

AU - Andoni, Alexandr

AU - Naor, Assaf

AU - Neiman, Ofer

N1 - Funding Information:
A. A. was supported in part by the NSF and the Simons Foundation. A. N. was supported in part by the BSF, the Packard Foundation and the Simons Foundation. O. N. was supported in part by the ISF and the European Union’s Seventh Framework Programme. Some of the results of the present article were announced in the extended abstract [2] that was presented in the 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). We refer to [2] for algorithmic context and applications of our results to theoretical computer science.
Publisher Copyright:
© 2018 Société Mathématique de France. Tous droits réservés.
Copyright:
Copyright 2018 Elsevier B.V., All rights reserved.

PY - 2018/5/1

Y1 - 2018/5/1

N2 - For p ∈ (1; ∞) let Pp(ℝ3) denote the metric space of all p-integrable Borel probability measures on ℝ3, equipped with the Wasserstein p metric Wp. We prove that for every ϵ > 0, every θ ∈ (0; 1/p] and every finite metric space (X, dX), the metric space (X; dX θ) embeds into Pp(ℝ3) with distortion at most 1 + ϵ. We show that this is sharp when p ∈ (1;2] in the sense that the exponent 1/p cannot be replaced by any larger number. In fact, for arbitrarily large n ∈ ℕ there exists an n-point metric space (Xn, dn) such that for every α ∈ (1/p, 1] any embedding of the metric space (Xn, dn α) into Pp (ℝ3) incurs distortion that is at least a constant multiple of (log n)α-1/p. These statements establish that there exists an Alexandrov space of nonnegative curvature, namely P2(ℝ3), with respect to which there does not exist a sequence of bounded degree expander graphs. It also follows that P2(ℝ3) does not admit a uniform, coarse, or quasisymmetric embedding into any Banach space of nontrivial type. Links to several longstanding open questions in metric geometry are discussed, including the characterization of subsets of Alexandrov spaces, existence of expanders, the universality problem for P2(ℝk), and the metric cotype dichotomy problem.

AB - For p ∈ (1; ∞) let Pp(ℝ3) denote the metric space of all p-integrable Borel probability measures on ℝ3, equipped with the Wasserstein p metric Wp. We prove that for every ϵ > 0, every θ ∈ (0; 1/p] and every finite metric space (X, dX), the metric space (X; dX θ) embeds into Pp(ℝ3) with distortion at most 1 + ϵ. We show that this is sharp when p ∈ (1;2] in the sense that the exponent 1/p cannot be replaced by any larger number. In fact, for arbitrarily large n ∈ ℕ there exists an n-point metric space (Xn, dn) such that for every α ∈ (1/p, 1] any embedding of the metric space (Xn, dn α) into Pp (ℝ3) incurs distortion that is at least a constant multiple of (log n)α-1/p. These statements establish that there exists an Alexandrov space of nonnegative curvature, namely P2(ℝ3), with respect to which there does not exist a sequence of bounded degree expander graphs. It also follows that P2(ℝ3) does not admit a uniform, coarse, or quasisymmetric embedding into any Banach space of nontrivial type. Links to several longstanding open questions in metric geometry are discussed, including the characterization of subsets of Alexandrov spaces, existence of expanders, the universality problem for P2(ℝk), and the metric cotype dichotomy problem.

UR - http://www.scopus.com/inward/record.url?scp=85049826705&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85049826705&partnerID=8YFLogxK

U2 - 10.24033/asens.2363

DO - 10.24033/asens.2363

M3 - Article

AN - SCOPUS:85049826705

VL - 51

SP - 657

EP - 700

JO - Annales Scientifiques de l'Ecole Normale Superieure

JF - Annales Scientifiques de l'Ecole Normale Superieure

SN - 0012-9593

IS - 3

ER -