Talks
Fall 2013

# Simple and Deterministic Matrix Sketches

Monday, September 16th, 2013 11:15 am12:00 pm

A sketch of a matrix $A$ is another matrix $B$ which is significantly smaller than $A$, but still approximates it well.
In this paper, we adapt a well known streaming algorithm for approximating item frequencies to the matrix sketching setting. The algorithm receives $n$ rows of a large matrix $A in R^{n imes m}$ one after the other, in a streaming fashion. It maintains a sketch $B in R^ { ell imes m}$ containing only $ell ll n$ rows but still guarantees that $A^TA pprox B^TB$. More accurately,
$$orall x, |x|=1 0 le |Ax|^2 - |Bx|^2 le 2|A|_{f}^2/ell$$
This algorithm's error decays proportionally to $1/ell$ using $O(m ell)$ space. In comparison, random-projection, hashing or sampling based algorithms produce convergence bounds proportional to $1/sqrt{ell}$. Sketch updates per row in $A$ require amortized $O(mell)$ operations and the algorithm is perfectly parallelizable. Our experiments corroborate the algorithm's scalability and improved convergence rate. The presented algorithm also stands out in that it is deterministic, simple to implement, and elementary to prove.