Snowflake universality of Wasserstein spaces

MaRDI QIDQ4584312zbMATH OpenFDO

Authors Alexandr Andoni, Assaf Naor, Ofer Neiman

Publication date 30 August 2018

Full work available at URL https://arxiv.org/abs/1509.08677, http://smf4.emath.fr/en/Publications/AnnalesENS/4_51/html/ens_ann-sc_51_657-700.php

zbMATH Keywords

Alexandrov spaceArens-Eells spaceearth mover distanceKantorovich-Rubinstein distanceLipschitz-free spaceMarkov typemetric cotype dichotomy problemmetric embeddingnonlinear spectral gapsnowflakes of metric spacestransportation costWasserstein distance

Mathematics Subject Classification ID

Geometric embeddings of metric spaces (30L05) Nonlinear classification of Banach spaces; nonlinear quotients (46B80) Embeddings of discrete metric spaces into Banach spaces; applications in topology and computer science (46B85) Spaces of measures (46E27) Global geometric and topological methods (à la Gromov); differential geometric analysis on metric spaces (53C23)

Abstract: For $pin(1,infty)$ let $mathscr{P}_p(mathbb{R}^3)$ denote the metric space of all $p$-integrable Borel probability measures on $mathbb{R}^3$, equipped with the Wasserstein $p$ metric $mathsf{W}_p$. We prove that for every $varepsilon>0$, every $hetain(0,1/p]$ and every finite metric space $(X,d_X)$, the metric space $(X,d_X^{heta})$ embeds into $mathscr{P}_p(mathbb{R}^3)$ with distortion at most $1+varepsilon$. We show that this is sharp when $pin(1,2]$ in the sense that the exponent $1/p$ cannot be replaced by any larger number. In fact, for arbitrarily large $ninmathbbN$ there exists an $n$-point metric space $(X_n,d_n)$ such that for every $alphain(1/p,1]$ any embedding of the metric space $(X_n,d_n^{a}lpha)$ into $mathscr{P}_p(mathbb{R}^3)$ incurs distortion that is at least a constant multiple of $(logn{)}^{alpha-1/p}$. These statements establish that there exists an Alexandrov space of nonnegative curvature, namely $mathscr{P}_{!2}(mathbb{R}^3)$, with respect to which there does not exist a sequence of bounded degree expander graphs. It also follows that $mathscr{P}_{!2}(mathbb{R}^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 $mathscr{P}_{!2}(mathbb{R}^k)$, and the metric cotype dichotomy problem.

Recommendations

• On isometric embeddings of Wasserstein spaces -- the discrete case
• On embedding expanders into \(\ell_p\) spaces
• A geometric study of Wasserstein spaces: Hadamard spaces
• A GEOMETRIC STUDY OF WASSERSTEIN SPACES: ULTRAMETRICS
• A geometric study of Wasserstein spaces: Euclidean spaces

Cites work

• \(L_p\) compression, traveling salesmen, and stable walks.
• A lower bound on the distortion of embedding planar metrics into Euclidean space
• A note on Markov type constants
• A NOTE ON NON-AMENABILITY OF ℬ(ℓ_p) FOR p=1,2
• A phase transition phenomenon between the isometric and isomorphic extension problems for Hölder functions betweenL_pspaces
• A reinforcement of property (T)
• A rigidity theorem in Alexandrov spaces with lower curvature bound
• A strengthened Banach property (T) and the fast Fourier transform
• Absolutely summing operators and translation invariant spaces of functions on compact abelian groups
• An alternative proof of Berg and Nikolaev's characterization of CAT(0)-spaces via quadrilateral inequality
• An application of metric cotype to quasisymmetric embeddings
• An introduction to the Ribe program
• An invitation to Alexandrov geometry. CAT(0) spaces
• Bilipschitz embeddings of metric spaces into space forms
• Curvature bounded below: a definition a la Berg-Nikolaev
• Embedding the diamond graph in L_p and dimension reduction in L₁
• Embeddings of Discrete Groups and the Speed of Random Walks
• Expander graphs and their applications
• Expanders with respect to Hadamard spaces and random graphs
• Extensions of Lipschitz maps into Hadamard spaces
• Factorization of operator valued analytic functions
• Fast Construction of Nets in Low-Dimensional Metrics and Their Applications
• Filling Riemannian manifolds
• Girth and Euclidean distortion
• scientific article; zbMATH DE number 3935689 (Why is no real title available?)
• scientific article; zbMATH DE number 44588 (Why is no real title available?)
• scientific article; zbMATH DE number 3507416 (Why is no real title available?)
• scientific article; zbMATH DE number 3597361 (Why is no real title available?)
• scientific article; zbMATH DE number 1095489 (Why is no real title available?)
• scientific article; zbMATH DE number 1128877 (Why is no real title available?)
• scientific article; zbMATH DE number 2020159 (Why is no real title available?)
• scientific article; zbMATH DE number 2051142 (Why is no real title available?)
• scientific article; zbMATH DE number 1749054 (Why is no real title available?)
• scientific article; zbMATH DE number 1385418 (Why is no real title available?)
• scientific article; zbMATH DE number 3442634 (Why is no real title available?)
• scientific article; zbMATH DE number 1909499 (Why is no real title available?)
• scientific article; zbMATH DE number 802809 (Why is no real title available?)
• scientific article; zbMATH DE number 3424629 (Why is no real title available?)
• scientific article; zbMATH DE number 3182580 (Why is no real title available?)
• Hyperbolicity, CAT(\(-1\))-spaces and the Ptolemy inequality
• Impossibility of sketching of the 3D transportation metric with quadratic cost
• Inequalities. A journey into linear analysis
• Kirszbraun's theorem and metric spaces of bounded curvature
• Lipschitz-free Banach spaces
• Locally decodable codes and the failure of cotype for projective tensor products
• Markov chains in smooth Banach spaces and Gromov-hyperbolic metric spaces
• Markov chains, Riesz transforms and Lipschitz maps
• Markov convexity and local rigidity of distorted metrics
• Markov type and threshold embeddings
• Markov type of Alexandrov spaces of non-negative curvature
• Mass transportation problems. Vol. 1: Theory. Vol. 2: Applications
• Maximum gradient embeddings and monotone clustering
• Metric cotype
• Metric Dichotomies
• Metric Spaces and Positive Definite Functions
• Metric spaces of lower bounded curvature
• Metric structures for Riemannian and non-Riemannian spaces. Transl. from the French by Sean Michael Bates. With appendices by M. Katz, P. Pansu, and S. Semmes. Edited by J. LaFontaine and P. Pansu
• Metric structures in \(L_1\): dimension, snowflakes, and average distortion
• New Banach space properties of the disc algebra and \(H^{\infty}\)
• Nonembeddability theorems via Fourier analysis
• Nonlinear spectral calculus and super-expanders
• Nonpositive Curvature and the Ptolemy Inequality
• On a distance characterization of A. D. Aleksandrov spaces of nonpositive curvature
• On embedding expanders into \(\ell_p\) spaces
• On Lipschitz embedding of finite metric spaces in Hilbert space
• On the geometry of metric measure spaces. I
• On the nonexistence of uniform homeomorphisms between \(L^ p\)-spaces
• On uniformly homeomorphic normed spaces
• Planar Earthmover Is Not in L₁
• PLANE WITH $A_{\infty}$ -WEIGHTED METRIC NOT BILIPSCHITZ EMBEDDABLE TO ${\bb R}^n$
• Poincaré inequalities and rigidity for actions on Banach spaces
• Poincaré inequalities, embeddings, and wild groups.
• PTOLEMAIC SPACES AND CAT(0)
• Quasilinearization and curvature of Aleksandrov spaces
• Quasisymmetric embeddings of metric spaces
• Random walk in random groups.
• Remarks on non linear type and Pisiers inequality
• Ricci curvature for metric-measure spaces via optimal transport
• Rigidity of quasi-isometries for symmetric spaces and Euclidean buildings
• Sphere equivalence, Banach expanders, and extrapolation
• Strong Banach property (T) for simple algebraic groups of higher rank
• The boundary correspondence under quasiconformal mappings
• THE GEOMETRY OF DISSIPATIVE EVOLUTION EQUATIONS: THE POROUS MEDIUM EQUATION
• The metrical interpretation of superreflexivity in Banach spaces
• The Ptolemaic inequality in Hilbert geometries
• The wreath product of $\mathbb {Z}$ with $\mathbb {Z}$ has Hilbert compression exponent $\frac {2}{3}$
• Une remarque sur les ensembles de Helson

Cited in

(24)

• Vertical perimeter versus horizontal perimeter
• Markov type constants, flat tori and Wasserstein spaces
• An introduction to the Ribe program
• On quantitative sphere equivalence and extrapolation phenomenon
• Applications of optimal transportation in the natural sciences. Abstracts from the workshop held February 21--27, 2021 (online meeting)
• An intrinsic characterization of five points in a CAT(0) space
• Nonpositive curvature is not coarsely universal
• On isometric embeddings of Wasserstein spaces -- the discrete case
• Spectral calculus and Lipschitz extension for barycentric metric spaces
• Metric \(X_{p}\) inequalities
• A geometric study of Wasserstein spaces: Hadamard spaces
• Lipschitz-free spaces on finite metric spaces
• Moments of the Distance Between Independent Random Vectors
• Finite flat spaces
• Old and new challenges in Hadamard spaces
• A non-geodesic analogue of Reshetnyak's majorization theorem
• Quantitative stability of optimal transport maps under variations of the target measure
• Bi-Lipschitz embeddings of the space of unordered \(m\)-tuples with a partial transportation metric
• Coarse embeddability of Wasserstein space and the space of persistence diagrams
• Inequalities on six points in a \(\mathrm{CAT}(0)\) space
• On the existence of Monge maps for the Gromov-Wasserstein problem
• Stability of homomorphisms, coverings and cocycles. II: Examples, applications and open problems
• Coarse embeddings of quotients by finite group actions
• Unstable optimal transport maps

This page was built for publication: Snowflake universality of Wasserstein spaces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4584312)