Measured descent: A new embedding method for finite metrics (Q2571745): Difference between revisions

The authors devise a new embedding method, called measure descent. It is based on decomposing a metric space locally, according to the density of a certain probability measure. The method unifies and refines the methods of Bourgain and of Rao for constructing Fr{échet}-type embeddings, that is embeddings where each coordinate is proportional to the distance from some subset of the metric space. The authors prove that any \(n\)-point metric space \(X\) embeds into \(\ell _2\) with distortion \(O(\sqrt{\alpha _X \log n})\), where \(\alpha _X\) is a geometric estimate on the decomposability of \(X\) satisfying \(\alpha _X = O(\log n)\) and \(\alpha _X = O(\log \lambda _X)\), where \(\lambda _X\) (\(\leq n\)) is the doubling constant of \(X\). Thus the result recovers \textit{J.\,Bourgain}'s theorem [Isr.\ J.\ Math.\ 52, 46--52 (1985; Zbl 0657.46013)]. The next result answers affirmatively a question posed by K.\,Feige about volume-respecting embeddings. The notion of volume-respecting embeddings was introduced by \textit{U.\,Feige} [J.~Comput.\ Syst.\ Sci.\ 60, No.\,3, 510--539 (2000; Zbl 0958.68191)] as follows. Let \(S\) be a \(k\)-point subset of \(X\). Define \[ \text{vol} (S) = \sup \{\text{vol}_{k-1} (\text{conv}\;g(S)) \mid g : S \to L_2 \text{ is } 1\text{-Lipschitz} \}, \] where \(\text{conv}\) denotes the convex hull and \(\text{vol} _{k-1}\) denotes the \((k-1)\)-dimensional volume with respect to the Euclidean structure induced by \(L_2\). A~\(1\)-Lipschitz mapping \(f : S \to L_2\) is called \((k, \eta)\)-volume-respecting if, for every \(k\)-point subset \(S\) of \(X\), one has \[ \left( \text{vol} (S) / \text{vol} _{k-1} (\text{conv} \;f(S)) \right)^{1/(k-1)} \leq \eta. \] The authors prove that every \(n\)-point metric space \(X\) admits an embedding into \(L_2\) which is \((k, O(\sqrt{\alpha _X \log n}))\)-volume-respecting for every \(2\leq k \leq n\). Finally, the authors use their methods to improve a result of Rao and answer in the affirmative a question of Rabinovitch. Namely, they show that every \(n\)-point edge-weighted planar graph equipped with the shortest path metric embeds into \(\ell _{\infty}^{O(\log n)}\) with \(O(1)\) distortion.