Embeddings of schatten norms with applications to data streams

Abstract

Given an n×d matrix A, its Schatten-p norm, p ≥ 1, is defined as ||A||p = (σ i=1rank(A) σi(A)p)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,. ,Apoly(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 q1. 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,. ,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 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 Õ (min(n, d)2/D4) space.