# Note on bi-Lipschitz embeddings into normed spaces

Commentationes Mathematicae Universitatis Carolinae (1992)

- Volume: 33, Issue: 1, page 51-55
- ISSN: 0010-2628

## Access Full Article

top## Abstract

top## How to cite

topMatoušek, Jiří. "Note on bi-Lipschitz embeddings into normed spaces." Commentationes Mathematicae Universitatis Carolinae 33.1 (1992): 51-55. <http://eudml.org/doc/247376>.

@article{Matoušek1992,

abstract = {Let $(X,d)$, $(Y,\rho )$ be metric spaces and $f:X\rightarrow Y$ an injective mapping. We put $\Vert f\Vert _\{\operatorname\{Lip\}\} = \sup \lbrace \rho (f(x),f(y))/d(x,y); x,y\in X, x\ne y\rbrace $, and $\operatorname\{dist\}(f)= \Vert f\Vert _\{\operatorname\{Lip\}\}.\Vert f^\{-1\}\Vert _\{\operatorname\{Lip\}\}$ (the distortion of the mapping $f$). We investigate the minimum dimension $N$ such that every $n$-point metric space can be embedded into the space $\ell _\{\infty \}^N$ with a prescribed distortion $D$. We obtain that this is possible for $N\ge C(\log n)^2 n^\{3/D\}$, where $C$ is a suitable absolute constant. This improves a result of Johnson, Lindenstrauss and Schechtman [JLS87] (with a simpler proof). Related results for embeddability into $\ell _p^N$ are obtained by a similar method.},

author = {Matoušek, Jiří},

journal = {Commentationes Mathematicae Universitatis Carolinae},

keywords = {finite metric space; embedding of metric spaces; distortion; Lipschitz mapping; spaces $\ell _p$; finite metric space; embedding of metric spaces; Lipschitz mapping; minimum dimension; given distortion},

language = {eng},

number = {1},

pages = {51-55},

publisher = {Charles University in Prague, Faculty of Mathematics and Physics},

title = {Note on bi-Lipschitz embeddings into normed spaces},

url = {http://eudml.org/doc/247376},

volume = {33},

year = {1992},

}

TY - JOUR

AU - Matoušek, Jiří

TI - Note on bi-Lipschitz embeddings into normed spaces

JO - Commentationes Mathematicae Universitatis Carolinae

PY - 1992

PB - Charles University in Prague, Faculty of Mathematics and Physics

VL - 33

IS - 1

SP - 51

EP - 55

AB - Let $(X,d)$, $(Y,\rho )$ be metric spaces and $f:X\rightarrow Y$ an injective mapping. We put $\Vert f\Vert _{\operatorname{Lip}} = \sup \lbrace \rho (f(x),f(y))/d(x,y); x,y\in X, x\ne y\rbrace $, and $\operatorname{dist}(f)= \Vert f\Vert _{\operatorname{Lip}}.\Vert f^{-1}\Vert _{\operatorname{Lip}}$ (the distortion of the mapping $f$). We investigate the minimum dimension $N$ such that every $n$-point metric space can be embedded into the space $\ell _{\infty }^N$ with a prescribed distortion $D$. We obtain that this is possible for $N\ge C(\log n)^2 n^{3/D}$, where $C$ is a suitable absolute constant. This improves a result of Johnson, Lindenstrauss and Schechtman [JLS87] (with a simpler proof). Related results for embeddability into $\ell _p^N$ are obtained by a similar method.

LA - eng

KW - finite metric space; embedding of metric spaces; distortion; Lipschitz mapping; spaces $\ell _p$; finite metric space; embedding of metric spaces; Lipschitz mapping; minimum dimension; given distortion

UR - http://eudml.org/doc/247376

ER -

## References

top- Bourgain J., On Lipschitz embedding of finite metric spaces in Hilbert space, Israel J. Math. 52 (1985), 46-52. (1985) Zbl0657.46013MR0815600
- Bourgain J., Milman V., Wolfson H., On type of metric spaces, Trans. Amer. Math. Soc. 294 (1986), 295-317. (1986) Zbl0617.46024MR0819949
- Johnson W., Lindenstrauss J., Extensions of Lipschitz maps into a Hilbert space, Contemporary Math. 26 (Conference in modern analysis and probability) 189-206, Amer. Math. Soc., 1984. MR0737400
- Johnson W., Lindenstrauss J., Schechtman G., On Lipschitz embedding of finite metric spaces in low dimensional normed spaces, in: (J. Lindenstrauss, V.D. Milman eds.), Lecture Notes in Mathematics 1267, Springer-Verlag, 1987. Zbl0631.46016MR0907694
- Matoušek J., Lipschitz distance of metric spaces (in Czech), CSc. degree thesis, Charles University, 1990.
- Schoenberg I.J., Metric spaces and positive definite functions, Trans. Amer. Math. Soc. 44 (1938), 522-536. (1938) Zbl0019.41502MR1501980
- Spencer J., Ten Lectures on the Probabilistic Method, CBMS-NSF, SIAM 1987. Zbl0822.05060MR0929258

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.