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

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, . . . , x n X there exists a linear mapping L:X F, where F X is a linear subspace of dimension O(log n), such that x i - x j L(x i) - L(x j) O(1)x i - 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 2 2O(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 Y whose Euclidean distortion is at least 2 ((n)), where is the inverse Ackermann function. Copyright by SIAM.

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