The Johnson-Lindenstrauss Lemma Almost Characterizes Hilbert Space, But Not Quite Academic Article uri icon

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,...,xnX, there exists a linear mapping L:XF, where FX is a linear subspace of dimension O(log n), such that {double pipe}xi-xj{double pipe}{double pipe}L(xi)-L(xj){double pipe}O(1){dot operator}{double pipe}xi-xj{double pipe} 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,. 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 EnY whose Euclidean distortion is at least 2((n)), where is the inverse Ackermann function. 2009 Springer Science+Business Media, LLC.

published proceedings

  • DISCRETE & COMPUTATIONAL GEOMETRY

author list (cited authors)

  • Johnson, W. B., & Naor, A.

citation count

  • 7

publication date

  • April 2010