BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

Sketching and Streaming Matrix Norms Woodruff, David


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)

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International