Revisiting Co-Occurring Directions: Sharper Analysis and Efficient Algorithm for Sparse Matrices

Luo Luo, Cheng Chen, Guangzeng Xie, Haishan Ye

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:

  1. Buffering: Incoming sparse rows are stored in a buffer until a memory threshold is reached.
  2. Compression: A Subspace Power Method (SPM) is used to extract a low-rank approximation of the buffered sparse data efficiently.
  3. 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.

Figure 1: Relative spectral norm error vs. sketch size across various datasets. SCOD shows superior error reduction at smaller sketch sizes compared to traditional COD and FD-AMM.

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.

Figure 3: Log relative error vs. computation time (s) across multiple sparse datasets. SCOD consistently reaches lower error thresholds in significantly less time than the SFD-AMM baseline.

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

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.
BibTeX
@inproceedings{luo2021revisiting,
  author = {Luo Luo and Cheng Chen and Guangzeng Xie and Haishan Ye},
  title = {{Revisiting Co-Occurring Directions: Sharper Analysis and Efficient Algorithm for Sparse Matrices}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  url = {https://openreview.net/forum?id=xp1L0PR7ip},
}

Loading related content...

Figure