# Co-Occuring Directions Sketching for Approximate Matrix Multiply

arXiv: https://arxiv.org/abs/1610.07686 · HTML: https://mlsanity.com/paper/1610.07686/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Oct 2016.

## Built on by (most cited first, 1 of 1)

- [Multiplying Matrices Without Multiplying](https://mlsanity.com/paper/2106.10860/) (2021)

## Abstract (arXiv)

We introduce co-occurring directions sketching, a deterministic algorithm for approximate matrix product (AMM), in the streaming model. We show that co-occuring directions achieves a better error bound for AMM than other randomized and deterministic approaches for AMM. Co-occurring directions gives a 1 + ε -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