The Johnson-Lindenstrauss lemma almost characterizes Hilbert space, but not quite

DOI10.1007/s00454-009-9193-zzbMath1196.46013arXiv0807.1919OpenAlexW2133711056WikidataQ125027030 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

zbMATH Keywords

dimension reductioncotypetypedistortionBanach-Mazur distanceJohnson-Lindenstrauss lemma\(2\)-convexified Tsirelson spaceinverse Ackerman functionKwapień's theorem

Mathematics Subject Classification ID

Computational learning theory (68Q32) Local theory of Banach spaces (46B07) Image processing (compression, reconstruction, etc.) in information and communication theory (94A08) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Embeddings of discrete metric spaces into Banach spaces; applications in topology and computer science (46B85)

Related Items

A Gaussian small deviation inequality for convex functions, \( \varepsilon \)-isometric dimension reduction for incompressible subsets of \(\ell_p\), Some more twisted Hilbert spaces, Impossibility of dimension reduction in the nuclear norm, A space with no unconditional basis that satisfies the Johnson-Lindenstrauss lemma, Sampling, Metric Entropy, and Dimensionality Reduction, Euclidean arrangements in Banach spaces

Cites Work

• 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 ₁
• 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
• 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