TY - GEN

T1 - Ultra-low-dimensional embeddings for doubling metrics

AU - Chan, T. H.Hubert

AU - Gupta, Anupam

AU - Talwar, Kunal

PY - 2008

Y1 - 2008

N2 - We consider the problem of embedding a metric into low-dimensional Euclidean space. The classical theorems of Bourgain and of Johnson and Lindenstrauss imply that any metric on n points embeds into an O(log n)-dimensional Euclidean space with O(log n) distortion. Moreover, a simple "volume" argument shows that this bound is nearly tight: the uniform metric on n points requires Ω(log n/log log n) dimensions to embed with logarithmic distortion. It is natural to ask whether such a volume restriction is the only hurdle to low-dimensional low-distortion embeddings. Do doubling metrics, which do not have large uniform submetrics, embed in low dimensional Euclidean spaces with small distortion? In this paper, we answer the question positively and show that any doubling metric embeds into O(log log n) dimensions with o(log n) distortion. In fact, we give a suite of embeddings with a smooth trade-off between distortion and dimension: given an n-point metric (V, d) with doubling dimension dim D, and any target dimension T in the range Ω(dim D log log n) ≤T ≤ O(log n), we embed the metric into Euclidean space ℝ T with O(log n √dim D /T) distortion.

AB - We consider the problem of embedding a metric into low-dimensional Euclidean space. The classical theorems of Bourgain and of Johnson and Lindenstrauss imply that any metric on n points embeds into an O(log n)-dimensional Euclidean space with O(log n) distortion. Moreover, a simple "volume" argument shows that this bound is nearly tight: the uniform metric on n points requires Ω(log n/log log n) dimensions to embed with logarithmic distortion. It is natural to ask whether such a volume restriction is the only hurdle to low-dimensional low-distortion embeddings. Do doubling metrics, which do not have large uniform submetrics, embed in low dimensional Euclidean spaces with small distortion? In this paper, we answer the question positively and show that any doubling metric embeds into O(log log n) dimensions with o(log n) distortion. In fact, we give a suite of embeddings with a smooth trade-off between distortion and dimension: given an n-point metric (V, d) with doubling dimension dim D, and any target dimension T in the range Ω(dim D log log n) ≤T ≤ O(log n), we embed the metric into Euclidean space ℝ T with O(log n √dim D /T) distortion.

UR - http://www.scopus.com/inward/record.url?scp=58449106325&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=58449106325&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:58449106325

SN - 9780898716474

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 333

EP - 342

BT - Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms

T2 - 19th Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 20 January 2008 through 22 January 2008

ER -