Embedding Finite Metric Spaces in Low Dimension
Yair Bartal · 2006
This paper presents novel techniques that allow the solution to several open problems regarding embedding of finite metric spaces into Lp. We focus on proving near optimal bounds on the dimension with which arbitrary metric spaces embed into Lp. The dimension of the embedding is of very high importance in particular in applications and much effort has been invested in analyzing it. However, no previous result improved the bound on the dimension which can be derived from Bourgain’s embedding. We prove that any metric space on n points embeds into Lp with distortion O(log n) in dimension O(log n). This provides an optimal bound on the dimension of the embedding. Somewhat surprisingly, we show that a further small improvement is possible at a small price in the distortion, obtaining an embedding with distortion O(log 1+θ n) in optimal dimension O(θ −1 log n / log log n), for any θ> 0. It is worth noting that with the small loss in the distortion this improves upon the best known embedding of arbitrary spaces into Euclidean space, where dimension reduction is used. Our techniques also allow to obtain the optimal distortion for embedding into Lp with nearly optimal dimension. For any 1 ≤ p ≤ ∞ and any 1 ≤ k ≤ p, we give an embedding into Lp with distortion O(⌈log n/k⌉) in dimension 2 O(k) log n. 1