Note on bi-Lipschitz embeddings into normed spaces
Matoušek, Jiří
Commentationes Mathematicae Universitatis Carolinae, Tome 33 (1992), p. 51-55 / Harvested from Czech Digital Mathematics Library
Access to full text
Full (PDF)

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.

Publié le : 1992-01-01
Classification:  46B07,  46B20,  46B25,  46B99,  54C25,  54E35 
@article{118470,
     author = {Ji\v r\'\i\ Matou\v sek},
     title = {Note on bi-Lipschitz embeddings into normed spaces},
     journal = {Commentationes Mathematicae Universitatis Carolinae},
     volume = {33},
     year = {1992},
     pages = {51-55},
     zbl = {0758.46019},
     mrnumber = {1173746},
     language = {en},
     url = {http://dml.mathdoc.fr/item/118470}
}

Matoušek, Jiří. Note on bi-Lipschitz embeddings into normed spaces. Commentationes Mathematicae Universitatis Carolinae, Tome 33 (1992) pp. 51-55. http://gdmltest.u-ga.fr/item/118470/

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

Bourgain J.; Milman V.; Wolfson H. On type of metric spaces, Trans. Amer. Math. Soc. 294 (1986), 295-317. (1986) | MR 0819949 | Zbl 0617.46024

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 0737400

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 0907694 | Zbl 0631.46016

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) | MR 1501980 | Zbl 0019.41502

Spencer J. Ten Lectures on the Probabilistic Method, CBMS-NSF, SIAM 1987. | MR 0929258 | Zbl 0822.05060