CoOccurring Directions Sketching for Approximate Matrix Multiply
[edit]
Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, PMLR 54:567575, 2017.
Abstract
We introduce cooccurring directions sketching, a deterministic algorithm for approximate matrix product (AMM), in the streaming model. We show that cooccurring directions achieves a better error bound for AMM than other randomized and deterministic approaches for AMM. Cooccurring directions gives a (1 + epsilon)  approximation of the optimal low rank approximation of a matrix product. Empirically our algorithm outperforms competing methods for AMM, for a small sketch size. We validate empirically our theoretical findings and algorithms.
Related Material


