File Download
There are no files associated with this item.
Supplementary

Citations:
 Scopus: 0
 Appears in Collections:
Conference Paper: Ultralowdimensional embeddings for doubling metrics
Title  Ultralowdimensional embeddings for doubling metrics 

Authors  
Issue Date  2008 
Citation  Proceedings Of The Annual AcmSiam Symposium On Discrete Algorithms, 2008, p. 333342 How to Cite? 
Abstract  We consider the problem of embedding a metric into lowdimensional 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 lowdimensional lowdistortion 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 tradeoff between distortion and dimension: given an npoint 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 Identifier  http://hdl.handle.net/10722/92652 
References 
DC Field  Value  Language 

dc.contributor.author  Chan, THH  en_HK 
dc.contributor.author  Gupta, A  en_HK 
dc.contributor.author  Talwar, K  en_HK 
dc.date.accessioned  20100917T10:53:05Z   
dc.date.available  20100917T10:53:05Z   
dc.date.issued  2008  en_HK 
dc.identifier.citation  Proceedings Of The Annual AcmSiam Symposium On Discrete Algorithms, 2008, p. 333342  en_HK 
dc.identifier.uri  http://hdl.handle.net/10722/92652   
dc.description.abstract  We consider the problem of embedding a metric into lowdimensional 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 lowdimensional lowdistortion 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 tradeoff between distortion and dimension: given an npoint 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.language  eng  en_HK 
dc.relation.ispartof  Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms  en_HK 
dc.title  Ultralowdimensional embeddings for doubling metrics  en_HK 
dc.type  Conference_Paper  en_HK 
dc.identifier.email  Chan, THH:hubert@cs.hku.hk  en_HK 
dc.identifier.authority  Chan, THH=rp01312  en_HK 
dc.description.nature  link_to_subscribed_fulltext   
dc.identifier.scopus  eid_2s2.058449106325  en_HK 
dc.relation.references  http://www.scopus.com/mlt/select.url?eid=2s2.058449106325&selection=ref&src=s&origin=recordpage  en_HK 
dc.identifier.spage  333  en_HK 
dc.identifier.epage  342  en_HK 
dc.identifier.scopusauthorid  Chan, THH=12645073600  en_HK 
dc.identifier.scopusauthorid  Gupta, A=35738763000  en_HK 
dc.identifier.scopusauthorid  Talwar, K=8955044700  en_HK 