Planar earthmover is not in L1

Assaf Naor; Gideon Schechtman

doi:10.1137/05064206X

Planar earthmover is not in L₁

Assaf Naor, Gideon Schechtman

Mathematics

Research output: Contribution to journal › Article › peer-review

Abstract

We show that any L₁ embedding of the transportation cost (a.k.a. Earthmover) metric on probability measures supported on the grid {0,1,..., n}² ⊆ ℝ² incurs distortion Ω (√log n). We also use Fourier analytic techniques to construct a simple L₁ embedding of this space which has distortion O(log n).

Original language	English (US)
Pages (from-to)	804-826
Number of pages	23
Journal	SIAM Journal on Computing
Volume	37
Issue number	3
DOIs	https://doi.org/10.1137/05064206X
State	Published - 2007

Keywords

Earthmover metric
Metric embeddings
Nearest neighbor search

ASJC Scopus subject areas

General Computer Science
General Mathematics

Access to Document

10.1137/05064206X

Cite this

@article{c5c5a75fe77044f5a9e7c888fdf399ee,

title = "Planar earthmover is not in L1",

abstract = "We show that any L1 embedding of the transportation cost (a.k.a. Earthmover) metric on probability measures supported on the grid {0,1,..., n}2 ⊆ ℝ2 incurs distortion Ω (√log n). We also use Fourier analytic techniques to construct a simple L1 embedding of this space which has distortion O(log n).",

keywords = "Earthmover metric, Metric embeddings, Nearest neighbor search",

author = "Assaf Naor and Gideon Schechtman",

year = "2007",

doi = "10.1137/05064206X",

language = "English (US)",

volume = "37",

pages = "804--826",

journal = "SIAM Journal on Computing",

issn = "0097-5397",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "3",

}

TY - JOUR

T1 - Planar earthmover is not in L1

AU - Naor, Assaf

AU - Schechtman, Gideon

PY - 2007

Y1 - 2007

N2 - We show that any L1 embedding of the transportation cost (a.k.a. Earthmover) metric on probability measures supported on the grid {0,1,..., n}2 ⊆ ℝ2 incurs distortion Ω (√log n). We also use Fourier analytic techniques to construct a simple L1 embedding of this space which has distortion O(log n).

AB - We show that any L1 embedding of the transportation cost (a.k.a. Earthmover) metric on probability measures supported on the grid {0,1,..., n}2 ⊆ ℝ2 incurs distortion Ω (√log n). We also use Fourier analytic techniques to construct a simple L1 embedding of this space which has distortion O(log n).

KW - Earthmover metric

KW - Metric embeddings

KW - Nearest neighbor search

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

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

U2 - 10.1137/05064206X

DO - 10.1137/05064206X

M3 - Article

AN - SCOPUS:46449112099

SN - 0097-5397

VL - 37

SP - 804

EP - 826

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 3

ER -