Please use this identifier to cite or link to this item:
Full metadata record
DC FieldValueLanguage
dc.contributor.authorLi, Yien
dc.contributor.authorWoodruff, David P.en
dc.identifier.citationLi, Y., & Woodruff, D. P. (2017). Embeddings of Schatten norms with applications to data streams. LIPIcs–Leibniz International Proceedings in Informatics, 80, 60-. doi:10.4230/LIPIcs.ICALP.2017.60en
dc.description.abstractGiven 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 greater than or equal to 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 greater than or equal to 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 greater than or equal to 1 using O~(min(n, d)^2/D^4) space.en
dc.format.extent14 p.en
dc.relation.ispartofseriesLIPIcs–Leibniz International Proceedings in Informaticsen
dc.rights© 2017 The Author(s) (Leibniz International Proceedings in Informatics). Licensed under Creative Commons License CC-BY.en
dc.subjectData Stream Algorithmsen
dc.titleEmbeddings of Schatten norms with applications to data streamsen
dc.typeJournal Articleen
dc.contributor.schoolSchool of Physical and Mathematical Sciencesen
dc.description.versionPublished versionen
item.fulltextWith Fulltext-
Appears in Collections:SPMS Journal Articles
Files in This Item:
File Description SizeFormat 
Embeddings of Schatten norms with applications to data streams.pdf534.88 kBAdobe PDFThumbnail

Citations 20

Updated on Feb 26, 2024

Page view(s) 50

Updated on Mar 3, 2024

Download(s) 50

Updated on Mar 3, 2024

Google ScholarTM




Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.