Li, Yi ;
Woodruff, David P.
Embeddings of Schatten Norms with Applications to Data Streams
Abstract
Given an n×d matrix A, its Schattenp norm, p >= 1, is defined as A_p = (sum_{i=1}^rank(A) sigma(i)^p）^{1/p} where sigma_i(A) is the ith largest singular value of A. These norms have been studied in functional analysis in the context of noncommutative L_pspaces, 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_ip <= 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 spaceapproximation tradeoffs for the Schatten 1norm, showing in a data stream it is possible to estimate the Schatten1 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:160:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770415},
ISSN = {18688969},
year = {2017},
volume = {80},
editor = {Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7372},
URN = {urn:nbn:de:0030drops73726},
doi = {10.4230/LIPIcs.ICALP.2017.60},
annote = {Keywords: data stream algorithms, embeddings, matrix norms, sketching}
}
07.07.2017
Keywords: 

data stream algorithms, embeddings, matrix norms, sketching 
Seminar: 

44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Issue date: 

2017 
Date of publication: 

07.07.2017 