论文标题
空间有限的稀疏矩阵的近似乘法
Approximate Multiplication of Sparse Matrices with Limited Space
论文作者
论文摘要
由于大规模应用的出现，近似空间有限的矩阵乘法已受到了不断增加的关注。最近，基于流行的矩阵素描算法 - 频繁的方向，以前的工作引入了共归还方向（COD），以减少此问题的近似错误。尽管它享受两个输入矩阵$ x \ in \ mathbb {r}^{m_x \ times n} $和$ y \ in \ mathbb {r}^r}^{m_y \ times n} $ sizgs Size size size size smize，但它享受了两个输入矩阵$ x \ in \ mathbb {r}^{m_x \ times n} $和$ y \ in \ mathbb {r}^r}^{m_y \ times n} $ size size size size， $ o \ left（n（m_x+m_y+\ ell）\ ell \ right）$，对于大输入矩阵仍然很高。在本文中，我们建议通过利用输入矩阵的稀疏性来降低时间复杂性。关键思想是采用可以利用稀疏性的近似奇异值分解（SVD）方法来减少COD所需的QR分解数量。通过这种方式，我们开发了稀疏的共归因于方向，将时间复杂性降低到$ \ widetilde {o} \ left（（（（x）+\ nnz（y））\ ell+ell+el+el+n \ ell^el^2 \ right）$ priventation $ privenativation $ trespation $，而在$ o（$ o（m_x+m__ y）$ o（m_y）中，表示$ x $中的非零条目的数量，而$ \ widetilde {o} $表示法隐藏了常数因子以及parogarithmit cartional。理论分析表明，我们算法的近似误差几乎与COD的近似误差相同。此外，我们从经验上验证算法的效率和有效性。
Approximate matrix multiplication with limited space has received ever-increasing attention due to the emergence of large-scale applications. Recently, based on a popular matrix sketching algorithm -- frequent directions, previous work has introduced co-occuring directions (COD) to reduce the approximation error for this problem. Although it enjoys the space complexity of $O((m_x+m_y)\ell)$ for two input matrices $X\in\mathbb{R}^{m_x\times n}$ and $Y\in\mathbb{R}^{m_y\times n}$ where $\ell$ is the sketch size, its time complexity is $O\left(n(m_x+m_y+\ell)\ell\right)$, which is still very high for large input matrices. In this paper, we propose to reduce the time complexity by exploiting the sparsity of the input matrices. The key idea is to employ an approximate singular value decomposition (SVD) method which can utilize the sparsity, to reduce the number of QR decompositions required by COD. In this way, we develop sparse co-occuring directions, which reduces the time complexity to $\widetilde{O}\left((\nnz(X)+\nnz(Y))\ell+n\ell^2\right)$ in expectation while keeps the same space complexity as $O((m_x+m_y)\ell)$, where $\nnz(X)$ denotes the number of non-zero entries in $X$ and the $\widetilde{O}$ notation hides constant factors as well as polylogarithmic factors. Theoretical analysis reveals that the approximation error of our algorithm is almost the same as that of COD. Furthermore, we empirically verify the efficiency and effectiveness of our algorithm.
