Revisiting Co-Occurring Directions: Sharper Analysis and Efficient Algorithm for Sparse Matrices
This work addresses efficient computation for large-scale data processing, offering incremental improvements to existing deterministic sketching methods.
The paper tackles the problem of approximate matrix multiplication in the streaming model with limited memory, providing a tighter error bound for the co-occurring directions algorithm and proposing a more efficient variant for sparse matrices, achieving improved performance on real-world datasets.
We study the streaming model for approximate matrix multiplication (AMM). We are interested in the scenario that the algorithm can only take one pass over the data with limited memory. The state-of-the-art deterministic sketching algorithm for streaming AMM is the co-occurring directions (COD), which has much smaller approximation errors than randomized algorithms and outperforms other deterministic sketching methods empirically. In this paper, we provide a tighter error bound for COD whose leading term considers the potential approximate low-rank structure and the correlation of input matrices. We prove COD is space optimal with respect to our improved error bound. We also propose a variant of COD for sparse matrices with theoretical guarantees. The experiments on real-world sparse datasets show that the proposed algorithm is more efficient than baseline methods.