On approximating functions of the singular values in a stream

Abstract

For any real number p > 0, we nearly completely characterize the space complexity of estimating ||A||pp = Σni=1 σpi 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-9(ϵ) 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 poly(ϵ-1 log n) bits of space, which holds even in the turnstile data stream model. The latter is optimal up to poly(ϵ-1 logn) 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), Ω(n1/p-1-2/log n) for p ∈ [1,2) and Ω(n1-2/p) for p ∈ (2,∞). We note for p G∈(2, ∞), while our lower bound for even integers is the same, for other p in this range our lower bound is n1-g(ϵ), which is considerably stronger than the previous n1-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.