Near Optimal Frequent Directions for Sketching Dense and Sparse Matrices

Zengfeng Huang
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:2048-2057, 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^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 Liberty (2013) 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v80-huang18a, title = {Near Optimal Frequent Directions for Sketching Dense and Sparse Matrices}, author = {Huang, Zengfeng}, booktitle = {Proceedings of the 35th International Conference on Machine Learning}, pages = {2048--2057}, year = {2018}, editor = {Dy, Jennifer and Krause, Andreas}, volume = {80}, series = {Proceedings of Machine Learning Research}, month = {10--15 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v80/huang18a/huang18a.pdf}, url = {https://proceedings.mlr.press/v80/huang18a.html}, 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^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 Liberty (2013) 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.} }
Endnote
%0 Conference Paper %T Near Optimal Frequent Directions for Sketching Dense and Sparse Matrices %A Zengfeng Huang %B Proceedings of the 35th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2018 %E Jennifer Dy %E Andreas Krause %F pmlr-v80-huang18a %I PMLR %P 2048--2057 %U https://proceedings.mlr.press/v80/huang18a.html %V 80 %X 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^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 Liberty (2013) 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.
APA
Huang, Z.. (2018). Near Optimal Frequent Directions for Sketching Dense and Sparse Matrices. Proceedings of the 35th International Conference on Machine Learning, in Proceedings of Machine Learning Research 80:2048-2057 Available from https://proceedings.mlr.press/v80/huang18a.html.

Related Material