An average John theorem

of Linial, London and Rabinovich (1995), strengthens a theorem of Matouv{s}ek (1996) which resolved questions of Johnson and Lindenstrauss (1982), Bourgain (1985) and Arias-de-Reyna and Rodr{'{i}}guez-Piazza (1992), and answers negatively a question that was posed (for algorithmic purposes) by Andoni, Nguyen, Nikolov, Razenshteyn and Waingarten (2016).

Review text

The author uses the following definition: An infinite metric space \(({\mathcal{M}},d_{\mathcal{M}})\) embeds into a normed space \((Z,\|\cdot\|_Z)\) with quadratic average distortion \(D\) if for \textit{every} Borel probability measure \(\mu\) on \({\mathcal{M}}\) there exists a \(D\)-Lipschitz mapping \(f=f_\mu:{\mathcal{M}}\to Z\) that satisfies \[ \iint_{{\mathcal{M}}\times {\mathcal{M}}} \|f(x)-f(y)\|_{\!Z}^{2\phantom{p}}\, \mathrm{d}\mu(x)\, \mathrm{d}\mu(y)\ge \iint_{{\mathcal{M}}\times {\mathcal{M}}} d_{\mathcal{M}}(x,y)^2\, \mathrm{d} \mu(x) \, \mathrm{d}\mu(y). \] The \(\omega\)-snowflake, \(\omega\in(0,1]\), of a metric space \(({\mathcal{M}},d_{\mathcal{M}})\) is the metric space \(({\mathcal{M}},d_{\mathcal{M}}^\omega)\). The author proves (Theorem 1): For every integer \(k\ge 2\), the \(\frac12\)-snowflake of any \(k\)-dimensional normed space embeds into a Hilbert space with quadratic average distortion \(\mathsf{C}\sqrt{\log k}\), where \(\mathsf{C}>0\) is a universal constant. An extremely important feature of this result is that the distortion is logarithmic in \(k\). As the author shows, other conditions of the statement, namely, (1) \(\frac12\)-snowflakes and (2) lower estimate only on average, can be replaced by conditions which are closer to a bilipschitz embedding only at the price of replacing the logarithmic in \(k\) upper estimate for distortion by a power-type estimate. The author named the theorem above ``an average John theorem because of its similarity with the classical theorem of \textit{F. John} [Studies Essays, pres. to R. Courant, 187--204 (1948; Zbl 0034.10503)]: For every \(k\in\mathbb{N}\), any \(k\)-dimensional normed space admits a linear embedding into a Hilbert space with distortion at most \(\sqrt{k}\). The paper presents (1) generalizations of the mentioned above Theorem 1, (2) results showing that the obtained average John theorems are sharp in some directions, (3) applications of the obtained results to embeddability problems. The complete listing of all of the significant results obtained in the paper would be too long, we provide the author's summary instead: ``We deduce from this (optimal) statement that if an \(n\)-vertex expander embeds with average distortion \(D\ge 1\) into [a normed space] \(X\), then necessarily \(\dim(X)\ge n^{\Omega(1/D)}\), which is sharp by the work of \textit{W. B. Johnson} et al. [Lect. Notes Math. 1267, 177--184 (1987; Zbl 0631.46016)]. This improves over the previously best-known bound \(\dim(X)\ge C (\log n)^2/D^2\) of \textit{N. Linial} et al. [Combinatorica 15, No. 2, 215--245 (1995; Zbl 0827.05021)], strengthens a theorem of \textit{J. Matoušek} [Isr. J. Math. 93, 333--344 (1996; Zbl 0851.46007)] which resolved questions of \textit{W. B. Johnson} and \textit{J. Lindenstrauss} [Contemp. Math. 26, 189--206 (1984; Zbl 0539.46017)], \textit{J. Bourgain} [Isr. J. Math. 52, 46--52 (1985; Zbl 0657.46013)] and \textit{J. Arias de Reyna} and \textit{L. Rodríguez-Piazza} [Isr. J. Math. 79, No. 1, 103--111 (1992; Zbl 0807.46015)], and answers negatively a question that was posed (for algorithmic purposes) by \textit{A. Andoni} et al. [in: Proceedings of the 49th annual ACM SIGACT symposium on theory of computing, STOC '17, Montreal, QC, Canada, June 19--23, 2017. New York, NY: Association for Computing Machinery (ACM). 902--913 (2017; Zbl 1370.68066)]. The proof of the main result is based on nonlinear spectral gaps and duality (application of the Hahn-Banach theorem). The paper contains an extensive survey of related results and open problems. Some parts of this work were announced in [\textit{A. Naor}, LIPIcs -- Leibniz Int. Proc. Inform. 77, Article 50, 16 p. (2017; Zbl 1433.68312)].

Recommendations

Cites work

Cited in

(6)

This page was built for publication: An average John theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2048458)