Ultra-low-dimensional embeddings for doubling metrics

T. H.Hubert Chan, Anupam Gupta, Kunal Talwar

Research output: Contribution to journalArticlepeer-review

Abstract

We consider the problem of embedding a metric into low-dimensional Euclidean space. The classical theorems of Bourgain, and of Johnson and Lindenstrauss say 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: a uniform metric on n points requires nearly logarithmic number of dimensions to embed with logarithmic distortion. It is natural to ask whether such a volume restriction is the only hurdle to low-dimensional embeddings. In other words, do doubling metrics, that do not have large uniform submetrics, and thus no volume hurdles to low dimensional embeddings, embed in low dimensional Euclidean spaces with small distortion In this article, we give a positive answer to this question. We show how to embed any doubling metrics into O(log log n) dimensions with O(log n) distortion. This is the first embedding for doubling metrics into fewer than logarithmic number of dimensions, even allowing for logarithmic distortion. This result is one extreme point of our general trade-off between distortion and dimension: given an n-point metric (V,d) with doubling dimension dimD, and any target dimension T in the range (ΩdimD log log n) ≤ T O ≤ (log n), we show that the metric embeds into Euclidean space ℝT with O(log n dimD/T) distortion.

Original languageEnglish (US)
Article number21
JournalJournal of the ACM
Volume57
Issue number4
DOIs
StatePublished - Apr 1 2010

Keywords

  • Dimension reduction
  • Euclidean embedding
  • Metric spaces

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence

Cite this