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

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}, l d o t s, x_{n} i n X

there exists a linear mapping

L : X o F

, where

F s u b s e t e q X

is a linear subspace of dimension

O (l o g n)

, such that

| x_{i} - x_{j} | l e | L (x_{i}) - L (x_{j}) | l e O (1) c d o t | x_{i} - x_{j} |

for all

i, j i n 1, l d o t s, 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

2^{2^{O (l o g^{*} 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} s u b s e t e q Y

whose Euclidean distortion is at least

2^{O m e g a (a l p h a (n))}

, where

a l p h a

is the inverse Ackermann function.

Recommendations

Cites work

Cited in

(13)

This page was built for publication: The Johnson-Lindenstrauss lemma almost characterizes Hilbert space, but not quite