Embeddings of Schatten norms with applications to data streams
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)^{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 da...
Saved in:
Main Authors: | , |
---|---|
Other Authors: | |
Format: | Article |
Language: | English |
Published: |
2018
|
Subjects: | |
Online Access: | https://hdl.handle.net/10356/87845 http://hdl.handle.net/10220/46888 |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Institution: | Nanyang Technological University |
Language: | English |
id |
sg-ntu-dr.10356-87845 |
---|---|
record_format |
dspace |
spelling |
sg-ntu-dr.10356-878452023-02-28T19:35:05Z Embeddings of Schatten norms with applications to data streams Li, Yi Woodruff, David P. School of Physical and Mathematical Sciences Embeddings Data Stream Algorithms DRNTU::Science::Mathematics 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)^{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. Published version 2018-12-07T08:56:51Z 2019-12-06T16:50:40Z 2018-12-07T08:56:51Z 2019-12-06T16:50:40Z 2017 Journal Article 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 https://hdl.handle.net/10356/87845 http://hdl.handle.net/10220/46888 10.4230/LIPIcs.ICALP.2017.60 en LIPIcs–Leibniz International Proceedings in Informatics © 2017 The Author(s) (Leibniz International Proceedings in Informatics). Licensed under Creative Commons License CC-BY. 14 p. application/pdf |
institution |
Nanyang Technological University |
building |
NTU Library |
continent |
Asia |
country |
Singapore Singapore |
content_provider |
NTU Library |
collection |
DR-NTU |
language |
English |
topic |
Embeddings Data Stream Algorithms DRNTU::Science::Mathematics |
spellingShingle |
Embeddings Data Stream Algorithms DRNTU::Science::Mathematics Li, Yi Woodruff, David P. Embeddings of Schatten norms with applications to data streams |
description |
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)^{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. |
author2 |
School of Physical and Mathematical Sciences |
author_facet |
School of Physical and Mathematical Sciences Li, Yi Woodruff, David P. |
format |
Article |
author |
Li, Yi Woodruff, David P. |
author_sort |
Li, Yi |
title |
Embeddings of Schatten norms with applications to data streams |
title_short |
Embeddings of Schatten norms with applications to data streams |
title_full |
Embeddings of Schatten norms with applications to data streams |
title_fullStr |
Embeddings of Schatten norms with applications to data streams |
title_full_unstemmed |
Embeddings of Schatten norms with applications to data streams |
title_sort |
embeddings of schatten norms with applications to data streams |
publishDate |
2018 |
url |
https://hdl.handle.net/10356/87845 http://hdl.handle.net/10220/46888 |
_version_ |
1759854287926591488 |