Embeddings of Schatten Norms with Applications to Data Streams

Given an n × d matrix A, its Schatten-p norm, p ≥ 1, is defined as |A|p = left (sumi=1^textrmrank(A)σi(A)p right )1/p, where σi(A) is the i-th largest singular value of A. These norms have been studied in functional analysis in the context of non-commutative ℓ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 A1, ldots, A^operatornamepoly(nd) ∈ ℝn × d, suppose we want to construct a linear map L such that L(Ai) ∈ ℝn' × d' for each i, where n' ≤ n and d' ≤ d, and further, |Ai|p ≤ |L(Ai)|q ≤ Dp,q |Ai|p for a given approximation factor Dp,q and real number q ≥ 1. Then how large do n' and d' need to be as a function of Dp,q? We nearly resolve this question for every p, q ≥ 1, for the case where L(Ai) can be expressed as R · Ai · S, where R and S are arbitrary matrices that are allowed to depend on A1, ldots, At, that is, L(Ai) can be implemented by left and right matrix multiplication. Namely, for every p, q ≥ 1, we provide nearly matching upper and lower bounds on the size of n' and d' as a function of Dp,q. Importantly, our upper bounds are it oblivious, meaning that R and S do not depend on the Ai, while our lower bounds hold even if R and S depend on the Ai. 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 ≥ 1 using tildeO(min(n,d)2/D4) space.