|
Dimension reduction for hyperbolic space
Author(s):
Itai
Benjamini;
Yury
Makarychev
Journal:
Proc. Amer. Math. Soc.
137
(2009),
695-698.
MSC (2000):
Primary 51M09, 68W40
Posted:
September 12, 2008
Retrieve article in:
PDF
Abstract |
References |
Similar articles |
Additional information
Abstract:
A dimension reduction for hyperbolic space is established. When points are far apart, an embedding with bounded distortion into  is achieved.
References:
-
- 1.
- N. Ailon and B. Chazelle,
Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform,
Proc. of the 38th Annual ACM Symposium on Theory of Computing, ACM, New York, 2006, pp. 557-563. MR 2277181 (2007h:68074) - 2.
- M. Bonk and O. Schramm,
Embeddings of Gromov hyperbolic spaces,
Geom. Funct. Anal. 10 (2000), no. 2, 266-306. MR 1771428 (2001g:53077) - 3.
- J. Cannon, W. Floyd, R. Kenyon, and W. Parry,
Hyperbolic geometry,
Flavors of Geometry, Math. Sci. Res. Inst. Publ., 31, Cambridge Univ. Press, Cambridge, 1997, pp. 59-115. MR 1491098 (99c:57036) - 4.
- W. B. Johnson and J. Lindenstrauss,
Extensions of Lipschitz mappings into a Hilbert space,
Contemp. Math., 26, Amer. Math. Soc., Providence, RI (1984), 189-206. MR 0737400 (86a:46018) - 5.
- R. Krauthgamer and J. R. Lee,
Algorithms on negatively curved spaces,
Proc. of the 47th Symposium on Foundations of Computer Science, 2006, pp. 119-132. - 6.
- J. Matoušek.
Bi-Lipschitz embeddings into low-dimensional Euclidean spaces,
Comment. Math. Univ. Carolin. 31 (1990), no. 3, 589-600. MR 1078491 (91k:54056)
Similar Articles:
Retrieve articles in Proceedings of the American Mathematical Society
with MSC
(2000):
51M09, 68W40
Retrieve articles in all Journals with MSC
(2000):
51M09, 68W40
Additional Information:
Itai
Benjamini
Affiliation:
Microsoft Research - and - Department of Mathematics, The Weizmann Institute, Rehovot 76100, Israel
Email:
itai.benjamini@weizmann.ac.il
Yury
Makarychev
Affiliation:
Microsoft Research New England, One Memorial Drive, Cambridge, Massachusetts 02142
Email:
yurym@microsoft.com
DOI:
10.1090/S0002-9939-08-09714-1
PII:
S 0002-9939(08)09714-1
Received by editor(s):
January 15, 2008
Posted:
September 12, 2008
Communicated by:
Mario Bonk
Copyright of article:
Copyright
2008,
American Mathematical Society
The copyright for this article reverts to public domain after 28 years from publication.
|
Comments: webmaster@ams.org