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.   Our results considerably strengthen lower bounds in previous work for arbitrary (not necessarily sparse) matrices  A : the previous best lower bound was Ω(log n ) for  p ∈ (0,1), Ω( n  1/ p −1/2 /log n ) for  p ∈ [1,2) and Ω( n  1−2/ p  ) for  p ∈ (2,∞). We note for  p  ∈ (2, ∞), while our lower bound for even integers is the same, for other  p  in this range our lower bound is  n  1− g (є) , which is considerably stronger than the previous  n  1−2/ p   for small enough constant є > 0. We obtain similar near-linear lower bounds for Ky-Fan norms, eigenvalue shrinkers, and M-estimators, many of which could have been solvable in logarithmic space prior to our work.
['Yi Li', 'David P. Woodruff']
On approximating functions of the singular values in a stream