Abstract
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.
Introduction
In the era of big data, multiplying two massive matrices ($X$ and $Y$) to identify correlations is a fundamental task. However, when datasets are too large to fit in memory, standard multiplication becomes impossible. Approximate Matrix Multiplication (AMM) addresses this by creating small "sketches" of the matrices that can be multiplied as proxies for the full product.
The challenge is intensified in streaming environments, where an algorithm must process data row-by-row in a single pass with strictly limited memory. While "Frequent Directions" (FD) is effective for matrix squaring ($X^T X$), the general case ($X^T Y$) is more complex. The Co-Occurring Directions (COD) algorithm previously demonstrated strong empirical performance, but its theoretical foundations were pessimistic, failing to explain its success on data with low-rank structures. Additionally, standard COD implementations struggled with the computational overhead of massive, sparse datasets.
Methods
Sharper Theoretical Analysis
This paper provides a major theoretical upgrade by deriving a new spectral norm error bound for COD. Previous bounds relied on the total energy (Frobenius norm) of the matrices, which often overestimated error. The new analysis incorporates the approximate low-rank structure of the data. By using the Ky Fan $k$-norm, the authors proved that if the product $X^T Y$ is dominated by its top singular values, COD is significantly more accurate than previously theorized. Furthermore, the paper proves that COD is "space optimal," meaning no competing algorithm can achieve this level of accuracy with less memory.
Sparse Co-Occurring Directions (SCOD)
Standard COD is computationally expensive for sparse matrices because it requires frequent, dense Singular Value Decompositions (SVD). To solve this, the authors introduced SCOD, which utilizes a buffering system. SCOD stores incoming sparse rows until a buffer is full, then employs a Subspace Power Method (SPM) to compress the buffer into a low-rank sketch. This strategy minimizes expensive calculations, allowing the algorithm to handle sparse inputs with high speed while maintaining rigorous theoretical guarantees.
Experimental Evaluation
The authors evaluated SCOD on several large-scale, real-world cross-language datasets (APR, PAN, JRC, and EURO). These datasets consist of parliamentary proceedings, legal documents, and reviews represented as high-dimensional, sparse bag-of-words matrices.
Key Results: Accuracy and Efficiency
Across all tested datasets, SCOD and COD consistently achieved lower relative error for the same "sketch size" compared to randomized algorithms and deterministic baselines like FD-AMM.
Beyond accuracy, SCOD demonstrated a dramatic speedup on sparse data. For instance, on the EURO dataset, SCOD reached target error levels in roughly 100 seconds, whereas baseline methods were significantly slower. This efficiency proves that the co-occurring directions approach, when combined with intelligent buffering, is fundamentally better suited for $X^T Y$ operations than simply sketching concatenated matrices.
Conclusion
By closing the gap between theory and practice, this work establishes COD as a robust and optimal framework for streaming AMM. The introduction of SCOD further extends these benefits to the sparse data regime, offering a practical tool for large-scale correlation analysis. Future work may apply these sharper analysis techniques and buffering strategies to other complex tasks such as Canonical Correlation Analysis (CCA) and Spectral Co-clustering.
Summary updated