| Title:
|
Note on bi-Lipschitz embeddings into normed spaces (English) |
| Author:
|
Matoušek, Jiří |
| Language:
|
English |
| Journal:
|
Commentationes Mathematicae Universitatis Carolinae |
| ISSN:
|
0010-2628 (print) |
| ISSN:
|
1213-7243 (online) |
| Volume:
|
33 |
| Issue:
|
1 |
| Year:
|
1992 |
| Pages:
|
51-55 |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
finite metric space |
| Keyword:
|
embedding of metric spaces |
| Keyword:
|
distortion |
| Keyword:
|
Lipschitz mapping |
| Keyword:
|
spaces $\ell_p$ |
| MSC:
|
46B07 |
| MSC:
|
46B20 |
| MSC:
|
46B25 |
| MSC:
|
46B99 |
| MSC:
|
54C25 |
| MSC:
|
54E35 |
| idZBL:
|
Zbl 0758.46019 |
| idMR:
|
MR1173746 |
| . |
| Date available:
|
2009-01-08T17:53:28Z |
| Last updated:
|
2012-04-30 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/118470 |
| . |
| Reference:
|
[Bou85] Bourgain J.: On Lipschitz embedding of finite metric spaces in Hilbert space.Israel J. Math. 52 (1985), 46-52. Zbl 0657.46013, MR 0815600 |
| Reference:
|
[BMW86] Bourgain J., Milman V., Wolfson H.: On type of metric spaces.Trans. Amer. Math. Soc. 294 (1986), 295-317. Zbl 0617.46024, MR 0819949 |
| Reference:
|
[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 0737400 |
| Reference:
|
[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. Zbl 0631.46016, MR 0907694 |
| Reference:
|
[Ma89] Matoušek J.: Lipschitz distance of metric spaces (in Czech).CSc. degree thesis, Charles University, 1990. |
| Reference:
|
[Scho38] Schoenberg I.J.: Metric spaces and positive definite functions.Trans. Amer. Math. Soc. 44 (1938), 522-536. Zbl 0019.41502, MR 1501980 |
| Reference:
|
[Spe87] Spencer J.: Ten Lectures on the Probabilistic Method.CBMS-NSF, SIAM 1987. Zbl 0822.05060, MR 0929258 |
| . |
