  A central problem in data streams is to characterize which functions of an
underlying frequency vector can be approximated efficiently. Recently there has
been considerable effort in extending this problem to that of estimating
functions of a matrix that is presented as a data-stream. This setting
generalizes classical problems to the analogous ones for matrices. For example,
instead of estimating frequent-item counts, we now wish to estimate
"frequent-direction" counts. A related example is to estimate norms, which now
correspond to estimating a vector norm on the singular values of the matrix.
Despite recent efforts, the current understanding for such matrix problems is
considerably weaker than that for vector problems.
  We study a number of aspects of estimating matrix norms in a stream that have
not previously been considered: (1) multi-pass algorithms, (2) algorithms that
see the underlying matrix one row at a time, and (3) time-efficient algorithms.
Our multi-pass and row-order algorithms use less memory than what is provably
required in the single-pass and entrywise-update models, and thus give
separations between these models (in terms of memory). Moreover, all of our
algorithms are considerably faster than previous ones. We also prove a number
of lower bounds, and obtain for instance, a near-complete characterization of
the memory required of row-order algorithms for estimating Schatten $p$-norms
of sparse matrices.
