The Johnson–Lindenstrauss Lemma Almost Characterizes Hilbert Space, But Not Quite |
| |
Authors: | William B Johnson Assaf Naor |
| |
Institution: | 1. Texas A&M University, College Station, TX, 77843, USA 2. Courant Institute, New York, NY, 10012, USA
|
| |
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,…,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
22O(log*n)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
⊆Y whose Euclidean distortion is at least 2Ω(α(n)), where α is the inverse Ackermann function. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|