Open Collections

Sketching and Streaming Matrix Norms

Banff International Research Station for Mathematical Innovation and Discovery

Unlike estimating the norm of a vector in a stream, the memory required for estimating the norm of a matrix is less understood. Of interest is estimating the Schatten p-norm of an n x n matrix A, which is the p-norm of the vector of singular values of A. I'll discuss a number of works in this direction, which nearly resolve the memory required of the algorithm in certain cases, such as when A has O(n) non-zero entries, when the algorithm is required to be a linear sketch and p > 2, or when the algorithm is required to be an embedding. The techniques are sometimes based on communication complexity, and sometimes more direct arguments tailored for linear sketches. I'll also discuss the main remaining open questions. Based on works with Yi Li and Huy Nguyen (Soda '14, Stoc '16, Random '16, arXiv '17)

Mathematics; Computer science; Information and communication, circuits; Theoretical computer science

video/mp4

Author affiliation: IBM

2017-09-20

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/63073

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/