On approximating matrix norms in data streams

• Main Authors: Li, Yi, Nguyẽn, Huy L., Woodruff, David P.
• Other Authors: School of Physical and Mathematical Sciences
• Format: Article
• Language: English
• Published: 2021
• Subjects: Engineering::Computer science and engineering::Theory of computation::Analysis of algorithms and problem complexity; Schatten Norm; Matrix Norm
• Online Access: https://hdl.handle.net/10356/146275
• Institution: Nanyang Technological University

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...