2016/02/01 by Mina Ghashami, Ghashami, Mina, Edo Liberty +3
Computer Science · Engineering · #Blind Source Separation Techniques #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Indoor and Outdoor Localization Technologies #Sparse and Compressive Sensing Techniques
paper · pdf · doi:10.48550/arxiv.1602.00412
openalex publication_date 2016/02/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
This paper describes Sparse Frequent Directions, a variant of Frequent Directions for sketching sparse matrices. It resembles the original algorithm in many ways: both receive the rows of an input matrix An × d one by one in the streaming setting and compute a small sketch B ∈ Rℓ × d. Both share the same strong (provably optimal) asymptotic guarantees with respect to the space-accuracy tradeoff in the streaming setting. However, unlike Frequent Directions which runs in O(ndℓ) time regardless of the sparsity of the input matrix A, Sparse Frequent Directions runs in O (nnz(A)ℓ + nℓ2) time. Our analysis loosens the dependence on computing the Singular Value Decomposition (SVD) as a black box within the Frequent Directions algorithm. Our bounds require recent results on the properties of fast approximate SVD computations. Finally, we empirically demonstrate that these asymptotic improvements are practical and significant on real and synthetic data.