Impossibility of dimension reduction in the nuclear norm (Q2291451): Difference between revisions

Let \(\mathsf{S}_1\) denote the Schatten-von Neumann trace class, that is, the Banach space of all nuclear linear operators \(T:\ell_2\to \ell_2\) with its nuclear norm. The main result of the paper is that the space \(\mathsf{S}_1\) does not admit dimension reduction. The result is obtained in a stronger form, in terms of Lipschitz quotients. Dimension reduction in this paper is understood as in [\textit{A. Naor}, ``Metric dimension reduction: a snapshot of the Ribe program'', in: Proceedings of the ICM 2018. Volume I: Plenary Lectures. Hackensack, NJ: World Scientific Publications. 759--837 (2018; Zbl 1444.46019)]. Namely, for an infinite-dimensional normed space \(X\), denote by \(\mathsf{k}_n^\alpha(X)\) the minimum \(k\in \mathbb{N}\) such that, for any finite subset \(\mathcal{C}\subset X\) with \(|\mathcal{C}|=n\), there exists a \(k\)-dimensional linear subspace \(F\) of \(X\) into which \(\mathcal{C}\) embeds with distortion \(\alpha\). The space \(X\) is said to admit metric dimension reduction if there exists \(\alpha\in[1,\infty)\) such that \(\lim_{n\to\infty}(\log \mathsf{k}_n^\alpha(X))/\log n=0\). Information on dimension reduction is very scarce. In addition to the famous result of \textit{W. B. Johnson} and \textit{J. Lindenstrauss} [Contemp. Math. 26, 189--206 (1984; Zbl 0539.46017)], stating that \(\ell_2\) admits metric dimension reduction (in a stronger form), it is known [\textit{W. B. Johnson} and \textit{A. Naor}, Discrete Comput. Geom. 43, No. 3, 542--553 (2010; Zbl 1196.46013)] that some spaces which are in a sense very close to \(\ell_2\) also admit metric dimension reduction. In the other direction, it is known [\textit{W. B. Johnson} et al., Lect. Notes Math. 1267, 177--184 (1987; Zbl 0631.46016)] that \(\ell_\infty\) does not admit a metric dimension reduction and [\textit{B. Brinkman} and \textit{M. Charikar}, J. ACM 52, No. 5, 766--788 (2005; Zbl 1310.68199)] that \(\ell_1\) does not admit a metric dimension reduction. An example of subsets of \(\ell_1\) which are used to prove the result of \textit{B. Brinkman} and \textit{M. Charikar} [J. ACM 52, No. 5, 766--788 (2005; Zbl 1310.68199)] are, after a small modification of distance, isometric to certain recursive families of graphs. The authors of the present paper show that the same sets can be used for proving the fact that \(\mathsf{S}_1\) does not admit dimension reduction. Since \(\ell_1\) is isometric to a subspace of \(\mathsf{S}_1\), to achieve this goal the authors have to prove that these recursive families of graphs do not admit low-distortion embeddings into low-dimensional subspaces of \(\mathsf{S}_1\). This is achieved by comparing the behavior of Markov chains on low-dimensional subspaces of \(\mathsf{S}_1\) and on the recursive families of graphs. More precisely, the authors study the Markov \(2\)-convexity constants introduced in [\textit{J. R. Lee} et al., Geom. Funct. Anal. 18, No. 5, 1609--1659 (2009; Zbl 1171.05318)] and contrast their estimates [\textit{M. Mendel} and \textit{A. Naor}, J. Eur. Math. Soc. (JEMS) 15, No. 1, 287--337 (2013; Zbl 1266.46016)] for the recursive families of graphs with the result established in this paper that the Markov \(2\)-convexity constant of any finite dimensional linear subspace \(X\) of \(\mathsf{S}_1\) is at most a universal constant multiple of \(\sqrt{\log \mathrm{dim}(X)}\).