AISTATS 2017poster18 citations
Co-Occurring Directions Sketching for Approximate Matrix Multiply
Youssef Mroueh, Etienne Marcheret, Vaibahava Goel
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.
BibTeX
@InProceedings{pmlr-v54-mroueh17a,
title = {{Co-Occurring Directions Sketching for Approximate Matrix Multiply}},
author = {Mroueh, Youssef and Marcheret, Etienne and Goel, Vaibahava},
booktitle = {Proceedings of the 20th International Conference on Artificial Intelligence and Statistics},
pages = {567--575},
year = {2017},
editor = {Singh, Aarti and Zhu, Jerry},
volume = {54},
series = {Proceedings of Machine Learning Research},
month = {20--22 Apr},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v54/mroueh17a/mroueh17a.pdf},
url = {https://proceedings.mlr.press/v54/mroueh17a.html},
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.}
}