File Download
There are no files associated with this item.
Supplementary
-
Citations:
- Scopus: 0
- Appears in Collections:
Conference Paper: Ultra-low-dimensional embeddings for doubling metrics
Title | Ultra-low-dimensional embeddings for doubling metrics |
---|---|
Authors | |
Issue Date | 2008 |
Publisher | Society for Industrial and Applied Mathematics. |
Citation | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 2008, p. 333-342 How to Cite? |
Abstract | 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. |
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 | 2010-09-17T10:53:05Z | - |
dc.date.available | 2010-09-17T10:53:05Z | - |
dc.date.issued | 2008 | en_HK |
dc.identifier.citation | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 2008, p. 333-342 | en_HK |
dc.identifier.uri | http://hdl.handle.net/10722/92652 | - |
dc.description.abstract | 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. | en_HK |
dc.language | eng | en_HK |
dc.publisher | Society for Industrial and Applied Mathematics. | - |
dc.relation.ispartof | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms | en_HK |
dc.title | Ultra-low-dimensional 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.identifier.scopus | eid_2-s2.0-58449106325 | en_HK |
dc.relation.references | http://www.scopus.com/mlt/select.url?eid=2-s2.0-58449106325&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 |