论文标题
重新审视共发生的方向：稀疏矩阵的更清晰分析和有效算法
Revisiting Co-Occurring Directions: Sharper Analysis and Efficient Algorithm for Sparse Matrices
论文作者
论文摘要
我们研究了近似矩阵乘法（AMM）的流模型。我们对算法只能以有限的内存来掌握数据的情况感兴趣。流媒体AMM的最新确定性草图算法是共发生的方向（COD），其近似错误比随机算法要小得多，并且在经验上比其他确定性素描方法胜过其他确定性素描方法。在本文中，我们为COD提供了更严格的误差，该误差限制为COD，其领先期限认为潜在的近似低级别结构和输入矩阵的相关性。我们证明COD相对于我们改进的误差绑定是最佳空间。我们还提出了一种COD的变体，以提供具有理论保证的稀疏矩阵。现实世界中稀疏数据集的实验表明，所提出的算法比基线方法更有效。
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.
