02/02/2021

Revisiting Co-Occurring Directions: Sharper Analysis and Efficient Algorithm for Sparse Matrices

Luo Luo, Cheng Chen, Guangzeng Xie, Haishan Ye

Keywords:

Abstract Paper Similar Papers

Abstract: 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.

The video of this talk cannot be embedded. You can watch it here:
https://slideslive.com/38947971
(Link will open in new window)
 0
 0
 0
 0
  Share    
This is an embedded video. Talk and the respective paper are published at AAAI 2021 virtual conference. If you are one of the authors of the paper and want to manage your upload, see the question "My papertalk has been externally embedded..." in the FAQ section.

Comments

Post Comment
no comments yet
code of conduct: tbd Characters remaining: 140

Similar Papers

 0
 0
 0
 0
 3:12 
 0
 0
 0
 0
 19:26 
 0
 0
 0
 0
 3:27 
 0
 0
 0
 0
 3:14 
 0
 0
 0
 0
 11:13 
 0
 0
 0
 0
 14:03 
 0
 0
 0
 0
 3:00 
 0
 0
 1
 1
 14:45 
 0
 0
 0
 0
 1:00 
 0
 0
 0
 0
 14:02 
 0
 0
 0
 0
 15:00 
 0
 0
 0
 0
 15:02 
 0
 0
 0
 0
 4:41 
 0
 0
 0
 0
 5:00 
 0
 0
 0
 0
 19:18 
 0
 1
 1
 1
 5:22 
 0
 0
 0
 0
 4:56 
 0
 0
 0
 0
 3:20 
 0
 0
 0
 0
 12:29 
 0
 0
 0
 0
 14:04 
 0
 0
 0
 0
 12:44 
 0
 0
 0
 0
 5:47 
 0
 0
 0
 0
 14:24 
 0
 0
 0
 0
 3:05 
 0
 0
 0
 0
 4:50 
 0
 0
 0
 0
 14:44 
 0
 0
 0
 0
 14:44 
 0
 0
 0
 0
 13:02 
 0
 0
 0
 0
 15:31 
 0
 0
 0
 0
 4:51 
 0
 0
 0
 0
 13:29 
 0
 0
 0
 0
 7:26 
 0
 0
 0
 0
 14:32 
 0
 0
 0
 0
 13:06 
 0
 0
 0
 0
 19:34 
 0
 0
 0
 0
 15:10 
 0
 0
 0
 0
 14:27 
 0
 0
 0
 1
 5:20 
 0
 0
 0
 0
 5:12 
 0
 0
 0
 0
 5:04