File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Ultra-low-dimensional embeddings for doubling metrics

TitleUltra-low-dimensional embeddings for doubling metrics
Authors
Issue Date2008
Citation
Proceedings Of The Annual Acm-Siam Symposium On Discrete Algorithms, 2008, p. 333-342 How to Cite?
AbstractWe 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.
Persistent Identifierhttp://hdl.handle.net/10722/92652
References

 

DC FieldValueLanguage
dc.contributor.authorChan, THHen_HK
dc.contributor.authorGupta, Aen_HK
dc.contributor.authorTalwar, Ken_HK
dc.date.accessioned2010-09-17T10:53:05Z-
dc.date.available2010-09-17T10:53:05Z-
dc.date.issued2008en_HK
dc.identifier.citationProceedings Of The Annual Acm-Siam Symposium On Discrete Algorithms, 2008, p. 333-342en_HK
dc.identifier.urihttp://hdl.handle.net/10722/92652-
dc.description.abstractWe 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.en_HK
dc.languageengen_HK
dc.relation.ispartofProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithmsen_HK
dc.titleUltra-low-dimensional embeddings for doubling metricsen_HK
dc.typeConference_Paperen_HK
dc.identifier.emailChan, THH:hubert@cs.hku.hken_HK
dc.identifier.authorityChan, THH=rp01312en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.scopuseid_2-s2.0-58449106325en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-58449106325&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.spage333en_HK
dc.identifier.epage342en_HK
dc.identifier.scopusauthoridChan, THH=12645073600en_HK
dc.identifier.scopusauthoridGupta, A=35738763000en_HK
dc.identifier.scopusauthoridTalwar, K=8955044700en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats