Approximate Multiplication of Sparse Matrices with Limited Space
  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$. 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.
