Matrix Norms in Data Streams: Faster, Multi-Pass and Row-Order

摘要: 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 extending this that estimating a matrix presented as data-stream. This setting generalizes classical problems the analogous ones for matrices. For example, instead frequent-item counts, we now wish estimate "frequent-direction" counts. related example norms, correspond norm on singular values matrix. Despite recent efforts, current understanding such considerably weaker than problems. We study number aspects norms stream have not previously considered: (1) multi-pass algorithms, (2) algorithms see one row at time, and (3) time-efficient algorithms. Our row-order use less memory what provably required single-pass entrywise-update models, thus give separations between these models (in terms memory). Moreover, all our are faster previous ones. We also prove lower bounds, obtain instance, near-complete characterization Schatten $p$-norms sparse