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

Authors

  • Luo Luo Department of Mathematics, The Hong Kong University of Science and Technology
  • Cheng Chen Department of Computer Science and Engineering, Shanghai Jiao Tong University
  • Guangzeng Xie Academy for Advanced Interdisciplinary Studies, Peking University
  • Haishan Ye School of Management, Xi'an Jiaotong University

Keywords:

Matrix & Tensor Methods, Dimensionality Reduction/Feature Selection

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.

Downloads

Published

2021-05-18

How to Cite

Luo, L., Chen, C., Xie, G., & Ye, H. (2021). Revisiting Co-Occurring Directions: Sharper Analysis and Efficient Algorithm for Sparse Matrices. Proceedings of the AAAI Conference on Artificial Intelligence, 35(10), 8793-8800. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/17065

Issue

Section

AAAI Technical Track on Machine Learning III