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）^{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 |

Schools: | School of Physical and Mathematical Sciences |

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 | Size | Format | |
---|---|---|---|---|

Embeddings of Schatten norms with applications to data streams.pdf | 534.88 kB | Adobe PDF | View/Open |

#### SCOPUS^{TM}

Citations
20

12
Updated on Feb 26, 2024

#### Page view(s) 50

428
Updated on Mar 3, 2024

#### Download(s) 50

59
Updated on Mar 3, 2024

#### Google Scholar^{TM}

Check
#### Altmetric

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