File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Ultra-low-dimensional embeddings for doubling metrics

TitleUltra-low-dimensional embeddings for doubling metrics
Authors
KeywordsDimension reduction
Euclidean embedding
Metric spaces
Issue Date2010
PublisherAssociation for Computing Machinery, Inc. The Journal's web site is located at http://www.acm.org/jacm
Citation
Journal Of The Acm, 2010, v. 57 n. 4, article no. 21 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 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 dim D, and any target dimension T in the range (Ωdim D log log n) ≤ T O ≤ (log n), we show that the metric embeds into Euclidean space ℝ T with O(log n dim D/T) distortion. © 2010 ACM.
Persistent Identifierhttp://hdl.handle.net/10722/92647
ISSN
2015 Impact Factor: 1.803
2015 SCImago Journal Rankings: 2.509
ISI Accession Number ID
Funding AgencyGrant Number
NSFCCR-0122581
CCF-0448095
Alfred P. Sloan Fellowship
Funding Information:

The research of T.-H. Hubert Chan was partly supported by the NSF grant CCR-0122581 (The ALADDIN project), the NSF CAREER award CCF-0448095, and by an Alfred P. Sloan Fellowship. The research of A. Gupta was partly supported by the NSF CAREER award CCF-0448095, and by an Alfred P. Sloan Fellowship.

References

 

DC FieldValueLanguage
dc.contributor.authorChan, THHen_HK
dc.contributor.authorGupta, Aen_HK
dc.contributor.authorTalwar, Ken_HK
dc.date.accessioned2010-09-17T10:52:56Z-
dc.date.available2010-09-17T10:52:56Z-
dc.date.issued2010en_HK
dc.identifier.citationJournal Of The Acm, 2010, v. 57 n. 4, article no. 21en_HK
dc.identifier.issn0004-5411en_HK
dc.identifier.urihttp://hdl.handle.net/10722/92647-
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 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 dim D, and any target dimension T in the range (Ωdim D log log n) ≤ T O ≤ (log n), we show that the metric embeds into Euclidean space ℝ T with O(log n dim D/T) distortion. © 2010 ACM.en_HK
dc.languageengen_HK
dc.publisherAssociation for Computing Machinery, Inc. The Journal's web site is located at http://www.acm.org/jacmen_HK
dc.relation.ispartofJournal of the ACMen_HK
dc.subjectDimension reductionen_HK
dc.subjectEuclidean embeddingen_HK
dc.subjectMetric spacesen_HK
dc.titleUltra-low-dimensional embeddings for doubling metricsen_HK
dc.typeArticleen_HK
dc.identifier.emailChan, THH:hubert@cs.hku.hken_HK
dc.identifier.authorityChan, THH=rp01312en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1145/1734213.1734215en_HK
dc.identifier.scopuseid_2-s2.0-77952073941en_HK
dc.identifier.hkuros170689-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-77952073941&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume57en_HK
dc.identifier.issue4en_HK
dc.identifier.spagearticle no. 21-
dc.identifier.epagearticle no. 21-
dc.identifier.eissn1557-735X-
dc.identifier.isiWOS:000279362300002-
dc.publisher.placeUnited Statesen_HK
dc.identifier.scopusauthoridChan, THH=12645073600en_HK
dc.identifier.scopusauthoridGupta, A=8354044800en_HK
dc.identifier.scopusauthoridTalwar, K=8955044700en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats