Advances in metric embedding theory (Q5894374): Difference between revisions

The paper contains numerous improvements of the existing results on embeddings of metric spaces into Banach spaces. Many of these improvements are motivated by applications. One of the directions in which the existing results are improved is the following: many of the known results estimate the worst-case distortion, that is, if we restrict to non-contractive embeddings, one estimates the maximal expansion of distances. However, for many applications average expansion is more interesting. The authors construct an embedding (Theorem 2) which simultaneously achieves the best possible order of the worst-case Euclidean distortion and has uniformly bounded average distortion. The authors introduce several different notions of average distortion and prove some analogues of the above stated result for them. The authors improve the known bound for the dimension of low-distortion embeddings into \(\ell_p\) by proving (Theorem 4): For any \(1\leq p\leq\infty\), every \(n\)-point metric space embeds in \(\ell_p\) with distortion \(O(\log n)\) in dimension \(O(\log n)\). The authors prove the following result which connects the intrinsic dimension of a doubling space and its embedding dimension (Theorem 8): There exists a universal constant \(C\) such that for any \(n\)-point metric space \((X, d)\) and any \(C/\log\log n <\theta\leq 1\), there exists an embedding \(f :X\to\ell_p^D\) with distortion \(O(\log^{1+\theta}n)\) where \(D = O(\text{dim}(X)/\theta)\). The authors prove also interesting results on partial embeddings (the case where we care only about some of the distances) and on scaling distortion (the case where we allow relatively large distortions for relatively small amounts of distances). The main tool for the embedding theorems proved in this paper is the notion of uniformly padded probabilistic partitions of a metric space. This 100-page paper contains many other versions of the results mentioned above and some related results, the purpose of this review was only to mention some of the directions which were studied in the paper.