Abstract
We introduce co-occurring directions sketching, a deterministic algorithm for approximate matrix product (AMM), in the streaming model. We show that co-occurring directions achieves a better error bound and higher accuracy for smaller memory footprints than previous randomized or deterministic methods by intelligently "shrinking" the singular values of cross-correlation sketches.
Introduction
In modern data science, computing the product of two massive matrices $X$ and $Y$ is a fundamental task for finding correlations, especially in multimodal datasets like image-text pairs. However, as data scales, these matrices often exceed memory capacity or arrive as continuous streams. Approximate Matrix Multiplication (AMM) addresses this by creating small "sketches" $B_X$ and $B_Y$ such that $B_X B_Y^\top \approx XY^\top$.
While randomized methods like sampling or random projections are common, they often require large sketch sizes to mitigate high variance. Deterministic methods like "Frequent Directions" (FD) were originally designed for covariance approximation ($XX^\top$). Applying FD to AMM typically required concatenating $X$ and $Y$, which leads to sub-optimal error guarantees and ignores the specific joint structure of the two matrices.
Methods: Co-Occurring Directions (Co-D)
Co-occurring Directions (Co-D) is a deterministic streaming algorithm that maintains the distinct structures of $X$ and $Y$. The algorithm follows a four-step iterative process:
- Collect: New columns from the stream are inserted into sketch matrices $B_X$ and $B_Y$.
- Decompose: Upon reaching capacity, the algorithm performs a QR decomposition followed by an SVD on the reduced matrices to identify the principal directions of correlation.
- Shrink: A "noise level" is identified based on the median singular value. All singular values are reduced by this amount, effectively zeroing out at least half of the sketch columns to make room for new data.
- Repeat: This continues until the stream is exhausted.
By avoiding concatenation, Co-D focuses specifically on the joint correlation, leading to a spectral norm error bound of $\|XY^\top - B_X B_Y^\top\| \le \frac{2\|X\|_F \|Y\|_F}{\ell}$, where $\ell$ is the sketch size.
Experimental Evaluation
The authors evaluated Co-D against randomized baselines (Sampling, Random Projection, Hashing) and the deterministic FD-AMM on synthetic low-rank matrices and the real-world MS-COCO dataset.
Accuracy and the "Phase Transition"
A key finding is the "phase transition" in error performance. For low-rank data, Co-D's error drops sharply once the sketch size $\ell$ reaches the true rank of the product $XY^\top$.
As shown in the figures above, Co-D consistently outperforms FD-AMM. For instance, in the regime where $k_x=400$ and $k_y=40$, Co-D achieves near-zero error at $\ell=40$, whereas FD-AMM requires $\ell \approx 440$ to reach similar precision. This efficiency stems from Co-D's dependence on the rank of the product rather than the rank of the concatenation.
Computational Efficiency
Co-D is not only accurate but also efficient. Its running time scales as $O(n(m_x + m_y + \ell)\ell)$, making it faster than random projections and competitive with simple sampling methods.
Conclusion
Co-Occurring Directions provides a robust, deterministic alternative for streaming AMM. It offers superior error bounds and rank efficiency compared to existing methods, particularly when the underlying data has a low-rank structure. Future work may involve refining the theoretical bounds and exploring more robust shrinkage operators to handle high-noise environments.
Summary updated