Frequent Directions: Simple and Deterministic Matrix Sketching

Abstract

We describe a new algorithm called FrequentDirections for deterministic matrix sketching in the row-update model. The algorithm is presented an arbitrary input matrix A \in \mathbb{R}^{n \times d} one row at a time. It performs O(d\ell) operations per row and maintains a sketch matrix B \in \mathbb{R}^{\ell \times d} such that for any k < \ell, \|A^TA - B^TB \|_2 \leq \|A - A_k\|_F^2 / (\ell-k) {\;and\;} \|A - \pi_{B_k}(A)\|_F^2 \leq (1 + \frac{k}{\ell-k}) \|A-A_k\|_F^2. Here, A_k stands for the minimizer of \|A - A_k\|_F over all rank k matrices (similarly for B_k) and \pi_{B_k}(A) is the rank k matrix resulting from projecting A on the row span of B_k. We show that both of these bounds are the best possible for the space allowed. The summary is mergeable and hence trivially parallelizable. Moreover, FrequentDirections outperforms exemplar implementations of existing streaming algorithms in the space-error tradeoff. This paper combines, simplifies, and extends the results of Liberty [Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2013], Ghashami and Phillips [Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014], and Woodruff [Proceedings of the 27th Annual Conference on Advances in Neural Information Processing Systems, 2014].