Low Rank Approximation Lower Bounds in Row-Update Streams

We study low-rank approximation in the streaming model in which the rows of an n d matrix A are presented one at a time in an arbitrary order.