Co-Occuring Directions Sketching for Approximate Matrix Multiply
This work addresses efficient matrix computations in streaming settings, offering a deterministic alternative with improved accuracy, though it appears incremental as it builds on existing AMM methods.
The paper tackles the problem of approximate matrix multiplication (AMM) in the streaming model by introducing a deterministic algorithm called co-occurring directions sketching, which achieves a better error bound than existing randomized and deterministic methods and provides a (1 + ε)-approximation of the optimal low-rank approximation, with empirical validation showing outperformance for small sketch sizes.
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