Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/87845
Title: Embeddings of Schatten norms with applications to data streams
Authors: Li, Yi
Woodruff, David P.
Keywords: Embeddings
Data Stream Algorithms
DRNTU::Science::Mathematics
Issue Date: 2017
Source: Li, 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.60
Series/Report no.: LIPIcs–Leibniz International Proceedings in Informatics
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 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.
URI: https://hdl.handle.net/10356/87845
http://hdl.handle.net/10220/46888
DOI: 10.4230/LIPIcs.ICALP.2017.60
Rights: © 2017 The Author(s) (Leibniz International Proceedings in Informatics). Licensed under Creative Commons License CC-BY.
Fulltext Permission: open
Fulltext Availability: With 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
View/Open

SCOPUSTM   
Citations 20

7
Updated on Sep 6, 2020

Page view(s)

335
Updated on Aug 14, 2022

Download(s) 50

38
Updated on Aug 14, 2022

Google ScholarTM

Check

Altmetric


Plumx

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