Near Optimal Frequent Directions for Sketching Dense and Sparse Matrices
[edit]
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:20482057, 2018.
Abstract
Given a large matrix $A\in\real^{n\times d}$, we consider the problem of computing a sketch matrix $B\in\real^{\ell\times d}$ which is significantly smaller than but still well approximates $A$. We are interested in minimizing the covariance error $\norm{A^TAB^TB}_2.$We consider the problems in the streaming model, where the algorithm can only make one pass over the input with limited working space. The popular Frequent Directions algorithm of Liberty (2013) and its variants achieve optimal spaceerror tradeoff. However, whether the running time can be improved remains an unanswered question.In this paper, we almost settle the time complexity of this problem. In particular, we provide new spaceoptimal algorithms with faster running times. Moreover, we also show that the running times of our algorithms are nearoptimal unless the stateoftheart running time of matrix multiplication can be improved significantly.
Related Material


