Measured descent: A new embedding method for finite metrics

Robert Krauthgamer, James R. Lee, Manor Mendel, Assaf Naor

פרסום מחקרי: פרסום בכתב עתמאמר מכנסביקורת עמיתים

תקציר

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 J. Bourgain and S. Rao. 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. An an immediate corollary, we obtain an O(√log λ 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(logn)) 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 2 n).

שפה מקוריתאנגלית
עמודים (מ-עד)434-443
מספר עמודים10
כתב עתProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
סטטוס פרסוםפורסם - 2004
פורסם באופן חיצוניכן
אירועProceedings - 45th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2004 - Rome, איטליה
משך הזמן: 17 אוק׳ 200419 אוק׳ 2004

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Measured descent: A new embedding method for finite metrics'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי