  We adapt a well known streaming algorithm for approximating item frequencies
to the matrix sketching setting. The algorithm receives the rows of a large
matrix $A \in \R^{n \times m}$ one after the other in a streaming fashion. It
maintains a sketch matrix $B \in \R^ {1/\eps \times m}$ such that for any unit
vector $x$ [\|Ax\|^2 \ge \|Bx\|^2 \ge \|Ax\|^2 - \eps \|A\|_{f}^2 \.] Sketch
updates per row in $A$ require $O(m/\eps^2)$ operations in the worst case. A
slight modification of the algorithm allows for an amortized update time of
$O(m/\eps)$ operations per row. The presented algorithm stands out in that it
is: deterministic, simple to implement, and elementary to prove. It also
experimentally produces more accurate sketches than widely used approaches
while still being computationally competitive.
