Abstract
We study the streaming model for approximate matrix multiplication (AMM), focusing on deterministic sketching algorithms under memory constraints. We provide a tighter error bound for the state-of-the-art Co-Occurring Directions (COD) algorithm, accounting for low-rank structures and matrix correlations, and prove its space optimality. Furthermore, we introduce Sparse COD (SCOD), a variant optimized for sparse matrices. Empirical results on real-world datasets demonstrate that SCOD significantly outperforms existing baselines in efficiency.
Introduction
In large-scale machine learning, computing the product of massive matrices ($X^T Y$) is a fundamental task, often used to identify correlations between data modalities. When data arrives in a stream and exceeds memory capacity, Approximate Matrix Multiplication (AMM) sketching algorithms are employed to maintain a compressed representation.
Co-Occurring Directions (COD) is currently the leading deterministic algorithm for streaming AMM. Despite its empirical success, its theoretical foundations remained incomplete, with existing error bounds failing to reflect its performance on low-rank data. Additionally, standard COD is computationally expensive for sparse matrices. This work addresses these gaps by providing a sharper theoretical analysis and introducing an efficient sparse variant, SCOD.
Sharper Analysis of COD
The authors provide a new spectral norm error bound for COD that isolates the top $k$ singular values of the input matrices. Unlike previous bounds based on the Frobenius norm, this tighter bound explains COD's efficiency on matrices with an approximate low-rank structure, where error is primarily driven by the "tail" or residual noise.
Key theoretical findings include:
- Space Optimality: COD is proven to be space-optimal, requiring only $O(m(d_x + d_y))$ space to achieve the improved error bound.
- Performance Parity: The analysis shows that COD's error bound is comparable to the Frequent Directions (FD) algorithm in the $X=Y$ case, reconciling its mathematical theory with its practical performance.
Sparse Co-Occurring Directions (SCOD)
Processing sparse streams row-by-row typically forces data into dense matrix operations, destroying computational efficiency. SCOD overcomes this by:
- Buffering: Incoming sparse rows are stored in a buffer until a memory threshold is reached.
- Compression: A Subspace Power Method (SPM) is used to extract a low-rank approximation of the buffered sparse data efficiently.
- Shrinkage: COD’s singular-value shrinkage step is applied to the compressed representation, maintaining theoretical guarantees while drastically reducing compute time.
Experimental Evaluation
The efficiency of SCOD was evaluated on several large, sparse text datasets, including Amazon Product Reviews (APR), PAN-PC-11, JRC Acquis, and Europarl.
Sketch Size and Accuracy
SCOD consistently achieves lower relative spectral norm errors at smaller sketch sizes compared to baselines such as FD-AMM and SFD-AMM. As shown in Figure 1, the proposed algorithm maintains high accuracy even with limited memory.
Computational Efficiency
In terms of time-vs-error performance, SCOD reaches target error rates significantly faster than SFD-AMM. Standard COD and FD-AMM were excluded from time comparisons due to their prohibitive slowness on these sparse datasets, highlighting the necessity of the SCOD variant for practical applications.
Conclusion
This work bridges the gap between the theoretical analysis and empirical performance of the COD algorithm. By introducing SCOD, the authors provide a practical and theoretically sound solution for streaming AMM on sparse data. Future work includes applying these techniques to other models relying on heavy matrix operations, such as Canonical Correlation Analysis (CCA) and spectral co-clustering.
Summary updated