Planar Earthmover Is Not in L₁

DOI10.1137/05064206XMaRDI QIDQ3507521zbMATH OpenOpenAlexFDO

Authors Assaf Naor, Gideon Schechtman

Publication date 19 June 2008

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cs/0509074

zbMATH Keywords

coarse embeddingearthmover metricLipschitz embeddingtransportation cost distance

Mathematics Subject Classification ID

Local theory of Banach spaces (46B07) Convexity and finite-dimensional Banach spaces (including special norms, zonoids, etc.) (aspects of convex geometry) (52A21) Metric spaces, metrizability (54E35) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Abstract: We show that any $L_1$ embedding of the transportation cost (a.k.a. Earthmover) metric on probability measures supported on the grid ${0,1,\mathrm{...},n}^{2}subseteq{R}^2$ incurs distortion $Omega(sqrtlogn)$. We also use Fourier analytic techniques to construct a simple $L_1$ embedding of this space which has distortion $O(logn)$.

Recommendations

• The planar \(L_{p}\)-Minkowski problem for \(0<p<1\)
• On the planar \(L_p\)-Minkowski problem
• The planar Orlicz Minkowski problem in the \(L^1\)-sense
• Non-properly embedded H-planes in H^2 R
• Inapproximability for planar embedding problems
• Properties of the \(d\)-dimensional Earth mover's problem
• Some Constrained Notions of Planarity
• PLANE WITH $A_{\infty}$ -WEIGHTED METRIC NOT BILIPSCHITZ EMBEDDABLE TO ${\bb R}^n$
• The planar \(L_p\) dual Minkowski problem
• A nonlinear Lazarev-Lieb theorem: \(L^2\)-orthogonality via motion planning

Cited in

(47)

• A power law for the distortion of planar sets
• Heat flow and quantitative differentiation
• Isometric structure of transportation cost spaces on finite metric spaces
• Structure of the Lipschitz free \(p\)-spaces \(\mathcal{F}_p (\mathbb{Z}^d)\) and \(\mathcal{F}_p (\mathbb{R}^d)\) for \(0<p\leq 1\)
• Some remarks on Schauder bases in Lipschitz free spaces
• On relations between transportation cost spaces and _1
• Counts-of-counts similarity for prediction and search in relational data
• Lipschitz free \(p\)-spaces for \(0 < p < 1\)
• Impossibility of almost extension
• Isomorphisms between spaces of Lipschitz functions
• Nonembeddability theorems via Fourier analysis
• Lipschitz-free spaces and Schur properties
• Finitely additive measures and complementability of Lipschitz-free spaces
• On Lipschitz-free spaces over spheres of Banach spaces
• On the structure of Lipschitz-free spaces
• Hölder-Lipschitz norms and their duals on spaces with semigroups, with applications to earth mover's distance
• Tree metrics and their Lipschitz-free spaces
• Approximation properties and Schauder decompositions in Lipschitz-free spaces
• Regularized optimal transport and the rot mover's distance
• Sketching and embedding are equivalent for norms
• Snowflake universality of Wasserstein spaces
• Better embeddings for planar earth-mover distance over sparse sets
• The non-linear geometry of Banach spaces after Nigel Kalton
• On Schauder bases in Lipschitz-free spaces
• Free spaces over some proper metric spaces
• The metric approximation property and Lipschitz-free spaces over subsets of \(\mathbb{R}^N\)
• On the geometry of Banach spaces of the form \(\mathrm{Lip}_0(C(K))\)
• On large ℓ₁-sums of Lipschitz-free spaces and applications
• Purely 1-unrectifiable metric spaces and locally flat Lipschitz functions
• Lipschitz-free spaces on finite metric spaces
• Bourgain discretization using Lebesgue-Bochner spaces
• Products of Lipschitz-free spaces and applications
• Free spaces over countable compact metric spaces
• ISOMETRIC REPRESENTATION OF LIPSCHITZ‐FREE SPACES OVER CONVEX DOMAINS IN FINITE‐DIMENSIONAL SPACES
• Pełczyński space is isomorphic to the Lipschitz free space over a compact set
• Adaptive metric dimensionality reduction
• Stochastic approximation of lamplighter metrics
• 𝐿₁-distortion of Wasserstein metrics: A tale of two dimensions
• Wasserstein distance and metric trees
• Lipschitz functions on quasiconformal trees
• Bi-Lipschitz embeddings of the space of unordered \(m\)-tuples with a partial transportation metric
• On the Lipschitz operator ideal \(\operatorname{Lip}_0 \circ \mathcal{A} \circ \operatorname{Lip}_0\)
• On certain equivalences of metric spaces
• Lipschitz spaces over non-porous sets
• An isometric representation for the Lipschitz-free space of length spaces embedded in finite-dimensional spaces
• Bourgain's discretization theorem
• Hyperbolic metric spaces and stochastic embeddings

This page was built for publication: Planar Earthmover Is Not in $L_1$

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