Measured descent: A new embedding method for finite metrics
| dc.creator | Krauthgamer, Robert | |
| dc.creator | Lee, James R. | |
| dc.creator | Mendel, Manor | |
| dc.creator | Naor, Assaf | |
| dc.date | 2004-12-02 | |
| dc.date | 2005-08-18 | |
| dc.date.accessioned | 2026-07-07T06:23:09Z | |
| dc.date.available | 2026-07-07T06:23:09Z | |
| dc.description | We devise a new embedding technique, which we call measured descent, based on decomposing a metric space locally, at varying speeds, according to the density of some probability measure. This provides a refined and unified framework for the two primary methods of constructing Frechet embeddings for finite metrics, due to [Bourgain, 1985] and [Rao, 1999]. We prove that any n-point metric space (X,d) embeds in Hilbert space with distortion O(sqrt{alpha_X log n}), where alpha_X is a geometric estimate on the decomposability of X. As an immediate corollary, we obtain an O(sqrt{(log lambda_X) \log n}) distortion embedding, where λ_X is the doubling constant of X. Since λ_X\le n, this result recovers Bourgain's theorem, but when the metric X is, in a sense, ``low-dimensional,'' improved bounds are achieved. Our embeddings are volume-respecting for subsets of arbitrary size. One consequence is the existence of (k, O(log n)) volume-respecting embeddings for all 1 \leq k \leq n, which is the best possible, and answers positively a question posed by U. Feige. Our techniques are also used to answer positively a question of Y. Rabinovich, showing that any weighted n-point planar graph embeds in l_\infty^{O(log n)} with O(1) distortion. The O(log n) bound on the dimension is optimal, and improves upon the previously known bound of O((log n)^2). | |
| dc.description | 17 pages. No figures. Appeared in FOCS '04. To appeaer in Geometric & Functional Analysis. This version fixes a subtle error in Section 2.2 | |
| dc.identifier | https://arxiv.org/abs/cs/0412008 | |
| dc.identifier | http://arxiv.org/abs/cs/0412008 | |
| dc.identifier | Geom. Funct. Anal. 15(4):839-858, 2005 | |
| dc.identifier | doi:10.1007/s00039-005-0527-6 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/96132 | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | Metric Geometry | |
| dc.title | Measured descent: A new embedding method for finite metrics | |
| dc.type | text |