Embeddings of Schatten Norms with Applications to Data Streams

Given an $n\times d$ matrix $A$, its Schatten-$p$ norm, $p\ge 1$, is defined as $|A|p = \left (\sum{i=1}^{$\text{rank}$(A)}\sigma_i(A)^p \right )^{1/p}$,where$\sigma_i(A)$isthe$i$-thlargestsingularvalueof$A$. These norms have been studied in functional analysis in the context of non-commutative ${\mathrm{\ell }}_p$-spaces, and recently in data stream and linear sketching models of computation. Basic questions on the relations between these norms, such as their embeddability, are still open. Specifically, given a set of matrices $A^1, \ldots, A^{\operatorname{poly}(nd)} \in $\mathbb{R}$^{n \times d}$,supposewewanttoconstructalinearmap$L$suchthat$L(A^i) \in $\mathbb{R}$^{n’ \times d’}$foreach$i$,where$n’ \leq n$and$d’ \leq d$, and further, $\mathrm{\parallel }{A}^i{\mathrm{\parallel }}_p\le \mathrm{\parallel }L(A^i){\mathrm{\parallel }}_q\le D_{p,q}\mathrm{\parallel }{A}^i{\mathrm{\parallel }}_p$ for a given approximation factor $D_{p,q}$ and real number $q\ge 1$. Then how large do $n^{\mathrm{\prime }}$ and $d^{\mathrm{\prime }}$ need to be as a function of $D_{p,q}$? We nearly resolve this question for every $p,q\ge 1$, for the case where $L(A^i)$ can be expressed as $R\cdot A^i\cdot S$, where $R$ and $S$ are arbitrary matrices that are allowed to depend on $A^1,\dots ,A^t$, that is, $L(A^i)$ can be implemented by left and right matrix multiplication. Namely, for every $p,q\ge 1$, we provide nearly matching upper and lower bounds on the size of $n^{\mathrm{\prime }}$ and $d^{\mathrm{\prime }}$ as a function of $D_{p,q}$. Importantly, our upper bounds are {\it oblivious}, meaning that $R$ and $S$ do not depend on the $A^i$, while our lower bounds hold even if $R$ and $S$ depend on the $A^i$. As an application of our upper bounds, we answer a recent open question of Blasiok et al. about space-approximation trade-offs for the Schatten $1$-norm, showing in a data stream it is possible to estimate the Schatten-$1$ norm up to a factor of $D\ge 1$ using $\tilde{O}(\min (n,d{)}^2\mathrm{/}{D}^4)$ space.