Geodesic
Note on bi-Lipschitz embeddings into normed spaces
Commentationes Mathematicae Universitatis Carolinae, Tome 33 (1992) no. 1, pp. 51-55 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

Let $(X,d)$, $(Y,\rho)$ be metric spaces and $f:X\to Y$ an injective mapping. We put $\|f\|_{\operatorname{Lip}} = \sup \{\rho (f(x),f(y))/d(x,y); x,y\in X, x\neq y\}$, and $\operatorname{dist}(f)= \|f\|_{\operatorname{Lip}}.\| f^{-1}\|_{\operatorname{Lip}}$ (the {\sl 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\geq 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.
Let $(X,d)$, $(Y,\rho)$ be metric spaces and $f:X\to Y$ an injective mapping. We put $\|f\|_{\operatorname{Lip}} = \sup \{\rho (f(x),f(y))/d(x,y); x,y\in X, x\neq y\}$, and $\operatorname{dist}(f)= \|f\|_{\operatorname{Lip}}.\| f^{-1}\|_{\operatorname{Lip}}$ (the {\sl 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\geq 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.
Classification : 46B07, 46B20, 46B25, 46B99, 54C25, 54E35
Keywords: finite metric space; embedding of metric spaces; distortion; Lipschitz mapping; spaces $\ell_p$ 
@article{CMUC_1992_33_1_a6,
     author = {Matou\v{s}ek, Ji\v{r}{\'\i}},
     title = {Note on {bi-Lipschitz} embeddings into normed spaces},
     journal = {Commentationes Mathematicae Universitatis Carolinae},
     pages = {51--55},
     year = {1992},
     volume = {33},
     number = {1},
     mrnumber = {1173746},
     zbl = {0758.46019},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CMUC_1992_33_1_a6/}
}
TY  - JOUR
AU  - Matoušek, Jiří
TI  - Note on bi-Lipschitz embeddings into normed spaces
JO  - Commentationes Mathematicae Universitatis Carolinae
PY  - 1992
SP  - 51
EP  - 55
VL  - 33
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/CMUC_1992_33_1_a6/
LA  - en
ID  - CMUC_1992_33_1_a6
ER  - 
%0 Journal Article
%A Matoušek, Jiří
%T Note on bi-Lipschitz embeddings into normed spaces
%J Commentationes Mathematicae Universitatis Carolinae
%D 1992
%P 51-55
%V 33
%N 1
%U http://geodesic.mathdoc.fr/item/CMUC_1992_33_1_a6/
%G en
%F CMUC_1992_33_1_a6
Matoušek, Jiří. Note on bi-Lipschitz embeddings into normed spaces. Commentationes Mathematicae Universitatis Carolinae, Tome 33 (1992) no. 1, pp. 51-55. http://geodesic.mathdoc.fr/item/CMUC_1992_33_1_a6/

[Bou85] Bourgain J.: On Lipschitz embedding of finite metric spaces in Hilbert space. Israel J. Math. 52 (1985), 46-52. | MR | Zbl

[BMW86] Bourgain J., Milman V., Wolfson H.: On type of metric spaces. Trans. Amer. Math. Soc. 294 (1986), 295-317. | MR | Zbl

[JL84] 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. | MR

[JLS87] Johnson W., Lindenstrauss J., Schechtman G.: On Lipschitz embedding of finite metric spaces in low dimensional normed spaces. in: {\sl Geometrical aspects of functional analysis} (J. Lindenstrauss, V.D. Milman eds.), Lecture Notes in Mathematics 1267, Springer-Verlag, 1987. | MR | Zbl

[Ma89] Matoušek J.: Lipschitz distance of metric spaces (in Czech). CSc. degree thesis, Charles University, 1990.

[Scho38] Schoenberg I.J.: Metric spaces and positive definite functions. Trans. Amer. Math. Soc. 44 (1938), 522-536. | MR | Zbl

[Spe87] Spencer J.: Ten Lectures on the Probabilistic Method. CBMS-NSF, SIAM 1987. | MR | Zbl