Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: 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.

9
The categories of this paper are: nlin
33
The categories of this paper are: plasm-ph
25
The categories of this paper are: patt-sol
15
The categories of this paper are: nucl-ex
17
The categories of this paper are: q-fin
34
The categories of this paper are: chem-ph
32
The categories of this paper are: atom-ph
12
The categories of this paper are: nucl-th
19
The categories of this paper are: eess
26
The categories of this paper are: bayes-an
31
The categories of this paper are: ao-sci
14
The categories of this paper are: math-ph
30
The categories of this paper are: q-alg
7
The categories of this paper are: hep-th
10
The categories of this paper are: q-bio
23
The categories of this paper are: solv-int