Fréchet embeddings of negative type metrics

Sanjeev Arora; James R. Lee; Assaf Naor

doi:10.1007/s00454-007-9007-0

Fréchet embeddings of negative type metrics

Sanjeev Arora
, James R. Lee
, Assaf Naor

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

11 Scopus citations

Abstract

We show that every n-point metric of negative type (in particular, every n-point subset of L ₁) admits a Fréchet embedding into Euclidean space with distortion O(√log n · log log n), a result which is tight up to the O(log∈log∈n) factor, even for Euclidean metrics. This strengthens our recent work on the Euclidean distortion of metrics of negative into Euclidean space.

Original language	English (US)
Pages (from-to)	726-739
Number of pages	14
Journal	Discrete and Computational Geometry
Volume	38
Issue number	4
DOIs	https://doi.org/10.1007/s00454-007-9007-0
State	Published - Dec 2007

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Geometry and Topology
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Keywords

Distortion
Euclidean
L
Metric embeddings
Sparsest cut problem

Access to Document

10.1007/s00454-007-9007-0

Cite this

@article{35f66335742c4a4aad3ebe1188f35899,

title = "Fr{\'e}chet embeddings of negative type metrics",

abstract = "We show that every n-point metric of negative type (in particular, every n-point subset of L 1) admits a Fr{\'e}chet embedding into Euclidean space with distortion O(√log n · log log n), a result which is tight up to the O(log∈log∈n) factor, even for Euclidean metrics. This strengthens our recent work on the Euclidean distortion of metrics of negative into Euclidean space.",

keywords = "Distortion, Euclidean, L, Metric embeddings, Sparsest cut problem",

author = "Sanjeev Arora and Lee, \{James R.\} and Assaf Naor",

year = "2007",

month = dec,

doi = "10.1007/s00454-007-9007-0",

language = "English (US)",

volume = "38",

pages = "726--739",

journal = "Discrete and Computational Geometry",

issn = "0179-5376",

publisher = "Springer New York",

number = "4",

}

TY - JOUR

T1 - Fréchet embeddings of negative type metrics

AU - Arora, Sanjeev

AU - Lee, James R.

AU - Naor, Assaf

PY - 2007/12

Y1 - 2007/12

N2 - We show that every n-point metric of negative type (in particular, every n-point subset of L 1) admits a Fréchet embedding into Euclidean space with distortion O(√log n · log log n), a result which is tight up to the O(log∈log∈n) factor, even for Euclidean metrics. This strengthens our recent work on the Euclidean distortion of metrics of negative into Euclidean space.

AB - We show that every n-point metric of negative type (in particular, every n-point subset of L 1) admits a Fréchet embedding into Euclidean space with distortion O(√log n · log log n), a result which is tight up to the O(log∈log∈n) factor, even for Euclidean metrics. This strengthens our recent work on the Euclidean distortion of metrics of negative into Euclidean space.

KW - Distortion

KW - Euclidean

KW - L

KW - Metric embeddings

KW - Sparsest cut problem

UR - https://www.scopus.com/pages/publications/37249059917

UR - https://www.scopus.com/pages/publications/37249059917#tab=citedBy

U2 - 10.1007/s00454-007-9007-0

DO - 10.1007/s00454-007-9007-0

M3 - Article

AN - SCOPUS:37249059917

SN - 0179-5376

VL - 38

SP - 726

EP - 739

JO - Discrete and Computational Geometry

JF - Discrete and Computational Geometry

IS - 4

ER -

Fréchet embeddings of negative type metrics

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this