2017/02/18 by Yi Li, David P. Woodruff, Li, Yi +1 · 1 citation
Mathematics · Engineering · #Random Matrices and Applications #Sparse and Compressive Sensing Techniques #Advanced Combinatorial Mathematics
paper · pdf · doi:10.48550/arxiv.1702.05626
Given an n × d matrix A, its Schatten-p norm, p ≥ 1, is defined as ‖A‖p = (∑i=1^\textrmrank(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 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, …, 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 O(min(n,d)2/D4) space.