When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2017.60
URN: urn:nbn:de:0030-drops-73726
URL: http://drops.dagstuhl.de/opus/volltexte/2017/7372/
 Go to the corresponding LIPIcs Volume Portal

### Embeddings of Schatten Norms with Applications to Data Streams

 pdf-format:

### Abstract

Given an n×d matrix A, its Schatten-p norm, p >= 1, is defined as |A|_p = (sum_{i=1}^rank(A) sigma(i)^p&#65289;^{1/p} where sigma_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 L_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, ... , A_poly(nd) in R^{n x d}, suppose we want to construct a linear map L such that L(A_i) in R^{n' x d'} for each i, where n' < n and d' < d, and further, |A_i|p <= |L(A_i)|_q <= D_{p,q}|A_i|_p for a given approximation factor D_{p,q} and real number q >= 1. Then how large do n' and d' need to be as a function of D_{p,q}? We nearly resolve this question for every p, q >= 1, for the case where L(A_i) can be expressed as R*A_i*S, where R and S are arbitrary matrices that are allowed to depend on A_1, ... ,A_t, that is, L(A_i) 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 D_{p,q}. Importantly, our upper bounds are 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 >= 1 using O~(min(n, d)^2/D^4) space.

### BibTeX - Entry

```@InProceedings{li_et_al:LIPIcs:2017:7372,
author =	{Yi Li and David P. Woodruff},
title =	{{Embeddings of Schatten Norms with Applications to Data Streams}},
booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
pages =	{60:1--60:14},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-041-5},
ISSN =	{1868-8969},
year =	{2017},
volume =	{80},
editor =	{Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},