| The Johnson-Lindenstrauss lemma almost characterizes Hilbert space, but not quite (2009) | |||||||||||||||
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 x1,..., xn ∈ X there exists a linear mapping L: X → F, where F ⊆ X is a linear subspace of dimension O(log n), such that ‖xi − x j ‖ ≤ ‖L(xi) − L(x j) ‖ ≤ O(1) · ‖xi − x j ‖ for all i, j ∈ {1,..., 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 22O(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 En ⊆ Y whose Euclidean distortion is at least 2Ω(α(n)) , where α is the inverse Ackermann function. 1 | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||