The Johnson-Lindenstrauss lemma almost characterizes Hilbert space, but not quite (Q2380779): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 07:56, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The Johnson-Lindenstrauss lemma almost characterizes Hilbert space, but not quite |
scientific article |
Statements
The Johnson-Lindenstrauss lemma almost characterizes Hilbert space, but not quite (English)
0 references
12 April 2010
0 references
To solve a problem about Lipschitz extensions, \textit{W.\,Johnson} and \textit{J.\,Lindenstrauss} [``Extensions of Lipschitz mappings into a Hilbert space,'' Contemp.\ Math.\ 26, 189--206 (1984; Zbl 0539.46017)] proved that every Hilbert space \(X = H\) has the following property: \((JL)\)\quad For every \(K, D > 1\), \(n \geq 1\), \(x_1, \dots, x_n \in X\), there exist a linear subspace \(F \subseteq X\) with \(\dim F \leq K\, \log n\) and a linear map \(L \colon X \to F\) such that \[ \| x_i - x_j\| \leq \| L (x_i) - L (x_j)\| \leq D\,\|x_i - x_j\|\text{ for all }i,j = 1, \dots, n. \] It has appeared, in the course of the past ten years, that this result has important applications, not only in geometry of Banach spaces, but also in computer science. In the present paper, the authors show that, if \(X\) is a Banach space satisfying \((JL)\), then the Banach-Mazur distance \(d_E\) of every \(n\)-dimensional subspace \(E\) of \(X\) to \(\ell_2^n\) is less than \(2^{2^{c \log^\ast \! n}}\), where \(c = c (D, K)\) and \(\log^\ast \! x\) is the unique integer \(l\) such that \(a_l < x \leq a_{l + 1}\), with \(a_1 = 1\) and \(a_{j + 1} = {\text{ e}}^{a_j}\). The proof uses Kwapień's theorem and, more precisely, the fact that \(d_F \leq T_2 (F)\, C_2 (F)\), where \(T_2 (F)\) and \(C_2 (F)\) are the Gaussian type \(2\) and Gaussian cotype \(2\) constants of \(F\subseteq X\). The authors then use the fact that, if \(\dim F = k\), these constants can be computed with at most \(k(k + 1)/2\) vectors and a random procedure to get an upper bound for \(T_2 (F)\) and \(C_2 (F)\). In fact, if \(\Delta (n) = \sup\{d_E:E \subseteq X\) and \(\dim E \leq n\}\), then this upper bound is \(2D\Delta \big(4 K \log (k + 1)\big)\), and one gets the recursive inequality \(\Delta (n) \leq 4D^2 [\Delta \big(4 K \log (n + 1)\big)]^2\), which gives, by iteration, the claimed result \(\Delta (n) \leq 2^{2^{c \log^\ast \! n}}\). Since \(\Delta (n) = o\, (\log n)\), it follows, by a result of \textit{G.\,Pisier} [``Martingales with values in uniformly convex spaces,'' Isr.\ J.\ Math.\ 20, 326--350 (1975; Zbl 0344.46030)] that every Banach space satisfying \((JL)\) is superreflexive. On the other hand, the authors show that the \(2\)-convexified Tsirelson space \(T^{(2)}\) satisfies \((JL)\), though it is far from the Hilbert space: for every \(n \geq 1\), there is an \(n\)-dimensional subspace \(F_n\) of \(T^{(2)}\) such that \(d_{F_n} \geq 2^{c \alpha (n)}\), where \(c > 0\) is a universal constant and \(\alpha (n) \to \infty\) (actually, \(\alpha\) is well determined: it is the so-called inverse Ackerman function). The paper ends with several remarks and open questions.
0 references
Banach-Mazur distance
0 references
cotype
0 references
distortion
0 references
inverse Ackerman function
0 references
Johnson-Lindenstrauss lemma
0 references
Kwapień's theorem
0 references
type
0 references
\(2\)-convexified Tsirelson space
0 references
dimension reduction
0 references