On approximating functions of the singular values in a stream

For any real number p > 0, we nearly completely characterize the space complexity of estimating || A || p p = ∑ i =1 n σ i p for n × n matrices A in which each row and each column has O (1) non-zero entries and whose entries are presented one at a time in a data stream model. Here the σ i are the singular values of A , and when p ≥ 1, || A || p p is the p -th power of the Schatten p -norm. We show that when p is not an even integer, to obtain a (1+є)-approximation to || A || p p with constant probability, any 1-pass algorithm requires n 1− g (є) bits of space, where g (є) → 0 as є → 0 and є > 0 is a constant independent of n . However, when p is an even integer, we give an upper bound of n 1−2/ p (є −1 log n ) bits of space, which holds even in the turnstile data stream model. The latter is optimal up to (є −1 log n ) factors.

Authors

• Yi Li 0002
• David P. Woodruff

Keywords

• Schatten norms
• algorithms
• complexity
• data streams
• matrix norms