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...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Language: | English |
| Published: |
2018
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/87845 http://hdl.handle.net/10220/46888 |
| _version_ | 1826115172836573184 |
|---|---|
| author | Li, Yi Woodruff, David P. |
| author2 | School of Physical and Mathematical Sciences |
| author_facet | School of Physical and Mathematical Sciences Li, Yi Woodruff, David P. |
| author_sort | Li, Yi |
| collection | NTU |
| 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. |
| first_indexed | 2024-10-01T03:51:12Z |
| format | Journal Article |
| id | ntu-10356/87845 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T03:51:12Z |
| publishDate | 2018 |
| record_format | dspace |
| spelling | ntu-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 |
| spellingShingle | Embeddings Data Stream Algorithms DRNTU::Science::Mathematics Li, Yi Woodruff, David P. Embeddings of Schatten norms with applications to data streams |
| title | 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_short | Embeddings of Schatten norms with applications to data streams |
| title_sort | embeddings of schatten norms with applications to data streams |
| topic | Embeddings Data Stream Algorithms DRNTU::Science::Mathematics |
| url | https://hdl.handle.net/10356/87845 http://hdl.handle.net/10220/46888 |
| work_keys_str_mv | AT liyi embeddingsofschattennormswithapplicationstodatastreams AT woodruffdavidp embeddingsofschattennormswithapplicationstodatastreams |