## תקציר

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 Fréchet 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(√α_{X} · log n), where α _{X} is a geometric estimate on the decomposability of X. As an immediate corollary, we obtain an O(√α_{X} · log n) distortion embedding, where λ _{X} is the doubling constant of X. Since λ _{X} ≤ 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 ≤ k ≤ 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_{∞}^{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}).

שפה מקורית | אנגלית |
---|---|

עמודים (מ-עד) | 839-858 |

מספר עמודים | 20 |

כתב עת | Geometric and Functional Analysis |

כרך | 15 |

מספר גיליון | 4 |

מזהי עצם דיגיטלי (DOIs) | |

סטטוס פרסום | פורסם - אוג׳ 2005 |

פורסם באופן חיצוני | כן |

### הערה ביבליוגרפית

Funding Information:J.R.L. Supported by NSF grant CCR-0121555 and an NSF Graduate Research Fellowship.