On approximating matrix norms in data streams

• Main Authors: Li, Yi, Nguyẽn, Huy L., Woodruff, David P.
• 其他作者: School of Physical and Mathematical Sciences
• 格式: Article
• 語言: English
• 出版: 2021
• 主題: Engineering::Computer science and engineering::Theory of computation::Analysis of algorithms and problem complexity; Schatten Norm; Matrix Norm
• 在線閱讀: https://hdl.handle.net/10356/146275

This paper presents a systematic study of the space complexity of estimating the Schatten p-norms of an n×n matrix in the turnstile streaming model. Both kinds of space complexities, bit complexity and sketching dimension, are considered. Furthermore, two sketching models, general linear sketching a...