On approximating functions of the singular values in a stream
Yi Li, David P. Woodruff · 2016
For any real number p > 0, we nearly completely characterize the space complexity of estimating ||A||pp = ∑i=1n σip 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||pp 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||pp with constant probability, any 1-pass algorithm requires n1−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 n1−2/p (є−1logn) bits of space, which holds even in the turnstile data stream model. The latter is optimal up to (є−1 logn) factors.