Note on bi-Lipschitz embeddings into normed spaces

Jiří Matoušek

Commentationes Mathematicae Universitatis Carolinae (1992)

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

Abstract

top
Let ( X , d ) , ( Y , ρ ) be metric spaces and f : X → Y an injective mapping. We put ∥ f ∥ Lip = sup { ρ ( f ( x ) , f ( y ) ) / d ( x , y ) ; x , y ∈ X , x ≠ y } , and dist ( f ) = ∥ f ∥ Lip . ∥ f - 1 ∥ 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 ℓ ∞ N with a prescribed distortion D . We obtain that this is possible for N ≥ 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 ℓ p N are obtained by a similar method.

How to cite

top

Matouš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
  1. Bourgain J., On Lipschitz embedding of finite metric spaces in Hilbert space, Israel J. Math. 52 (1985), 46-52. (1985) Zbl0657.46013MR0815600
  2. Bourgain J., Milman V., Wolfson H., On type of metric spaces, Trans. Amer. Math. Soc. 294 (1986), 295-317. (1986) Zbl0617.46024MR0819949
  3. 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
  4. 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
  5. Matoušek J., Lipschitz distance of metric spaces (in Czech), CSc. degree thesis, Charles University, 1990. 
  6. Schoenberg I.J., Metric spaces and positive definite functions, Trans. Amer. Math. Soc. 44 (1938), 522-536. (1938) Zbl0019.41502MR1501980
  7. Spencer J., Ten Lectures on the Probabilistic Method, CBMS-NSF, SIAM 1987. Zbl0822.05060MR0929258

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.