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

William B. Johnson, Assaf Naor

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 ∥x i - xj∥ ≤ ∥L(xi) - L(x j)∥ ≤ O(1)·∥xi - xj∥ 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.

Original languageEnglish (US)
Title of host publicationProceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms
PublisherAssociation for Computing Machinery
Pages885-891
Number of pages7
ISBN (Print)9780898716801
DOIs
StatePublished - 2009
Event20th Annual ACM-SIAM Symposium on Discrete Algorithms - New York, NY, United States
Duration: Jan 4 2009Jan 6 2009

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Other

Other20th Annual ACM-SIAM Symposium on Discrete Algorithms
CountryUnited States
CityNew York, NY
Period1/4/091/6/09

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'The Johnson-Lindenstrauss lemma almost characterizes Hilbert space, but not quite'. Together they form a unique fingerprint.

Cite this