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

From MaRDI portal
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
    0 references
    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
    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
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references