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

DOI10.1007/S00454-009-9193-ZzbMATH Open1196.46013arXiv0807.1919OpenAlexW2133711056WikidataQ125027030 ScholiaQ125027030MaRDI QIDQ2380779FDOQ2380779

Authors: Assaf Naor, William B. Johnson 

Publication date: 12 April 2010

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Abstract: Let $X$ be a normed space that satisfies the Johnson-Lindenstrauss lemma (J-L lemma, in short) in the sense that for any integer $n$ and any $x_1,ldots,x_{n}inX$ there exists a linear mapping $L:XoF$, where $FsubseteqX$ is a linear subspace of dimension $O(logn)$, such that $|x_i-x_j|le|L(x_i)-L(x_j)|leO(1)cdot|x_i-x_j|$ for all $i,jin1,ldots,n$. We show that this implies that $X$ is almost Euclidean in the following sense: Every $n$-dimensional subspace of $X$ embeds into Hilbert space with distortion $2^{2^{O(lo{g}^{\ast }n)}}$. On the other hand, we show that there exists a normed space $Y$ which satisfies the J-L lemma, but for every $n$ there exists an $n$-dimensional subspace $E_{n}subseteqY$ whose Euclidean distortion is at least $2^{Omega(alpha(n))}$, where $alpha$ is the inverse Ackermann function.

Full work available at URL: https://arxiv.org/abs/0807.1919

Recommendations

• scientific article; zbMATH DE number 7051258
• A space with no unconditional basis that satisfies the Johnson-Lindenstrauss lemma
• A simple proof of the Johnson-Lindenstrauss extension theorem
• Extensions of Lipschitz mappings into a Hilbert space
• An elementary proof of a theorem of Johnson and Lindenstrauss

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Cites Work

• Extensions of Lipschitz mappings into a Hilbert space
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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\)
• Approximation of zonoids by zonotopes
• Metric structures in \(L_1\): dimension, snowflakes, and average distortion
• Embedding Subspaces of L 1 into l N 1
• On the impossibility of dimension reduction in l ₁
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Isomorphic characterizations of inner product spaces by orthogonal series with vector valued coefficients
• Tsirelson's space. With an appendix by J. Baker, O. Slotterbeck and R. Aron
• Title not available (Why is that?)
• Finite metric spaces needing high dimension for Lipschitz embeddings in Banach spaces
• Stable distributions, pseudorandom generators, embeddings, and data stream computation
• Title not available (Why is that?)
• On Lipschitz embedding of finite metric spaces in Hilbert space
• Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform
• Title not available (Why is that?)
• Title not available (Why is that?)
• Computing 2-summing norm with few vectors
• Banach lattices with property \(( H )\) and weak Hilbert spaces
• Title not available (Why is that?)
• Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces
• Finite dimensional subspaces of \(L_p\)
• On Tsirelson's space
• On the distortion required for embedding finite metric spaces into normed spaces
• Title not available (Why is that?)
• Title not available (Why is that?)
• A reflexive Banach space which is not sufficiently Euclidean
• Title not available (Why is that?)
• The Banach-Mazur distance between symmetric spaces
• The Banach space T and the fast growing hierarchy from logic

Cited In (13)

• A Gaussian small deviation inequality for convex functions
• \( \varepsilon \)-isometric dimension reduction for incompressible subsets of \(\ell_p\)
• On Lipschitz extension from finite subsets
• Title not available (Why is that?)
• A simple proof of the Johnson-Lindenstrauss extension theorem
• A different Johnson-Lindenstrauss space
• Euclidean arrangements in Banach spaces
• Some more twisted Hilbert spaces
• Sampling, Metric Entropy, and Dimensionality Reduction
• Some applications of Ball’s extension theorem
• The Johnson-Schechtman space has the 6-bounded approximation property
• A space with no unconditional basis that satisfies the Johnson-Lindenstrauss lemma
• Title not available (Why is that?)

This page was built for publication: The Johnson-Lindenstrauss lemma almost characterizes Hilbert space, but not quite

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2380779)