Skip to yearly menu bar Skip to main content


Poster

Near Optimal Frequent Directions for Sketching Dense and Sparse Matrices

Zengfeng Huang

Hall B #185

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 \emph{covariance error} $\norm{A^TA-B^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~\cite{liberty2013simple} and its variants achieve optimal space-error 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 space-optimal algorithms with faster running times. Moreover, we also show that the running times of our algorithms are near-optimal unless the state-of-the-art running time of matrix multiplication can be improved significantly.

Live content is unavailable. Log in and register to view live content