The Johnson-Lindenstrauss lemma almost characterizes Hilbert space, but not quite
DOI10.1007/s00454-009-9193-zzbMath1196.46013arXiv0807.1919WikidataQ125027030 ScholiaQ125027030MaRDI QIDQ2380779
Assaf Naor, William B. Johnson
Publication date: 12 April 2010
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/0807.1919
dimension reduction; cotype; type; distortion; Banach-Mazur distance; Johnson-Lindenstrauss lemma; \(2\)-convexified Tsirelson space; inverse Ackerman function; Kwapień's theorem
68Q32: Computational learning theory
46B07: Local theory of Banach spaces
94A08: Image processing (compression, reconstruction, etc.) in information and communication theory
68P30: Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)
46B85: Embeddings of discrete metric spaces into Banach spaces; applications in topology and computer science
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The Banach-Mazur distance between symmetric spaces
- On Tsirelson's space
- The Banach space T and the fast growing hierarchy from logic
- On Lipschitz embedding of finite metric spaces in Hilbert space
- Computing 2-summing norm with few vectors
- Banach lattices with property \(( H )\) and weak Hilbert spaces
- Tsirelson's space. With an appendix by J. Baker, O. Slotterbeck and R. Aron
- Martingales with values in uniformly convex spaces
- The dimension of almost spherical sections of convex bodies
- Embedding the diamond graph in \(L_p\) and dimension reduction in \(L_1\)
- Finite metric spaces needing high dimension for Lipschitz embeddings in Banach spaces
- Approximation of zonoids by zonotopes
- On the distortion required for embedding finite metric spaces into normed spaces
- Metric structures in \(L_1\): dimension, snowflakes, and average distortion
- Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform
- Embedding Subspaces of L 1 into l N 1
- Extensions of Lipschitz mappings into a Hilbert space
- Stable distributions, pseudorandom generators, embeddings, and data stream computation
- On the impossibility of dimension reduction in l 1
- A reflexive Banach space which is not sufficiently Euclidean
- Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces
- Isomorphic characterizations of inner product spaces by orthogonal series with vector valued coefficients
