TY - GEN

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

AU - Johnson, William B.

AU - Naor, Assaf

N1 - Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.

PY - 2009

Y1 - 2009

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=70349102481&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=70349102481&partnerID=8YFLogxK

U2 - 10.1137/1.9781611973068.96

DO - 10.1137/1.9781611973068.96

M3 - Conference contribution

AN - SCOPUS:70349102481

SN - 9780898716801

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 885

EP - 891

BT - Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms

PB - Association for Computing Machinery

T2 - 20th Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 4 January 2009 through 6 January 2009

ER -