Note on bi-Lipschitz embeddings into normed spaces
Jiřı́ Matoušek · Czech digital mathematics library · 1992
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 eq 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.