The Johnson-Lindenstrauss lemma almost characterizes Hilbert space, but not quite
| dc.creator | Johnson, William B. | |
| dc.creator | Naor, Assaf | |
| dc.date | 2008-07-11 | |
| dc.date.accessioned | 2026-07-07T09:53:07Z | |
| dc.date.available | 2026-07-07T09:53:07Z | |
| dc.description | 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\in X$ there exists a linear mapping $L:X\to F$, where $F\subseteq X$ is a linear subspace of dimension $O(\log n)$, such that $\|x_i-x_j\|\le\|L(x_i)-L(x_j)\|\le O(1)\cdot\|x_i-x_j\|$ for all $i,j\in \{1,\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(\log^*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\subseteq Y$ whose Euclidean distortion is at least $2^{Ω(α(n))}$, where $α$ is the inverse Ackermann function. | |
| dc.identifier | https://arxiv.org/abs/0807.1919 | |
| dc.identifier | http://arxiv.org/abs/0807.1919 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/165837 | |
| dc.subject | Functional Analysis | |
| dc.subject | Computational Geometry | |
| dc.subject | Metric Geometry | |
| dc.title | The Johnson-Lindenstrauss lemma almost characterizes Hilbert space, but not quite | |
| dc.type | text |