Paper Info
Title
Frequent Directions : Simple and Deterministic Matrix Sketching.
Abstract
We describe a new algorithm called FREQUENT DIRECTIONS for deterministic matrix sketching in the row-updates model. The algorithm is presented an arbitrary input matrix A is an element of R(n)d one row at a time. It performed O(dl) operations per row and maintains a sketch matrix B is an element of R-ld such that for any k<l, parallel to A(T)A-(BB)-B-T parallel to 2 <= A-A(k)parallel to(2)(F)/(l-k) and parallel to A-pi B-k(A)parallel to(2)(F)<=(1+k/l-k)parallel to A-A(k)parallel to(2)(F).Here, A(k) stands for the minimizer of parallel to A-A(k)parallel to(F) over all rank k matrices (similarly B-k) and pi B-k(A) is the rank k matrix resulting from projecting A on the row span of B-k. We show both of these bounds are the best possible for the space allowed. The summary is mergeable, and hence trivially parallelizable. Moreover, FREQUENT DIRECTIONS outperforms exemplar implementations of existing streaming algorithms in the space-error tradeoff. This paper combines, simplifies, and extends the results of Liberty [Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2013], Ghashami and Phillips [Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014], and Woodruff [Proceedings of the 27th Annual Conference on Advances in Neural Information Processing Systems, 2014].
Year
DOI
Venue
2015
10.1137/15M1009718
SIAM JOURNAL ON COMPUTING
Keywords
Field
DocType
matrix sketching,streaming,FREQUENT DIRECTIONS,covariance sketching,SVD
Parallelizable manifold,Singular value decomposition,Discrete mathematics,Combinatorics,Streaming algorithm,Matrix (mathematics),Mathematics
Journal
Volume
Issue
ISSN
45
5
0097-5397
Citations 
PageRank 
References 
4
0.39
15
Authors
4
Name
Order
Citations
PageRank
Mina Ghashami1110.82
Edo Liberty239724.83
Jeff M. Phillips353649.83
David P. Woodruff42156142.38