What is Matrix Sketching?

Matrix sketching is a method of preserving some aspects of a large matrix in a much smaller one. For example, take some very large matrix where or or both are huge and represent it as a smaller matrix such that is small. If you are familiar with the SVD an easy way to accomplish this would be to take the SVD and find the best rank- approximation of denoted . The problem here is sometimes we want guarantees on this approximation matrix but we don’t want the expensive computation of the SVD .

Frequent Directions to the Rescue!

Frequent Directions (FD) addresses both of these issues. FD is an algorithm invented by Edo Liberty.
It adapts the well known frequent items algorithm to matrices and provides some excellent guarantees on the relationship between the original matrix and the sketched matrix . More formally, the algorithm takes in a stream of ’s rows and maintains a sketch of a matrix with where:\begin{align} B^TB \prec A^TA \text{ and } ||A^TA-B^TB||_2 \leq 2||A||_f^2/\ell \end{align} The matrix can also be obtained in time and space. Which is considerably better than SVD. For a derivation of this bound and its complexity see the original paper PDF.

Experiments

I wanted to see for myself that the above bound holds in practice. To do this I performed FD on a matrix for and graphed the upper bound and in Figure 1. Indeed we see that

Next I wanted to see that FD is faster than SVD so I fixed , , and varied from to . The results are displayed in Figure 2.

You can find my Scala implementation of Frequent directions along with my experimental code at: FD Implementation.