Co-Occurring Directions Sketching for Approximate Matrix Multiply
Abstract
We introduce co-occurring directions sketching, a deterministic algorithm for approximate matrix product (AMM), in the streaming model. We show that co-occurring directions achieves a better error bound for AMM than other randomized and deterministic approaches for AMM. Co-occurring 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.
Cite
Text
Mroueh et al. "Co-Occurring Directions Sketching for Approximate Matrix Multiply." International Conference on Artificial Intelligence and Statistics, 2017.Markdown
[Mroueh et al. "Co-Occurring Directions Sketching for Approximate Matrix Multiply." International Conference on Artificial Intelligence and Statistics, 2017.](https://mlanthology.org/aistats/2017/mroueh2017aistats-co/)BibTeX
@inproceedings{mroueh2017aistats-co,
title = {{Co-Occurring Directions Sketching for Approximate Matrix Multiply}},
author = {Mroueh, Youssef and Marcheret, Etienne and Goel, Vaibhava},
booktitle = {International Conference on Artificial Intelligence and Statistics},
year = {2017},
pages = {567-575},
url = {https://mlanthology.org/aistats/2017/mroueh2017aistats-co/}
}