The JohnsonLindenstrauss lemma almost characterizes Hilbert space, but not quite
Conference Paper

 Overview

 Identity

 Additional Document Info

 View All

Overview
abstract

Let X be a normed space that satisfies the JohnsonLindenstrauss lemma (JL 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 ndimensional 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 JL lemma, but for every n there exists an ndimensional subspace E n ⊆ Y whose Euclidean distortion is at least 2 Ω(α(n)), where α is the inverse Ackermann function. Copyright © by SIAM.
author list (cited authors)

Johnson, W. B., Naor, A., & SIAM, A.
complete list of authors

Johnson, William BNaor, AssafSIAM, ACM
publication date
Identity
International Standard Book Number (ISBN) 13
Additional Document Info