Frequent Directions : Simple and Deterministic Matrix Sketching

2015/01/08 by Mina Ghashami, Ghashami, Mina, Edo Liberty +5 · 8 citations
Computer Science · Engineering · #68W40 (Primary) #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques #cs.DS #msc:68W40

paper · pdf · doi:10.48550/arxiv.1501.01711

28 pages , This paper contains Frequent Directions algorithm (see arXiv:1206.0594) and relative error bound on it (see arXiv:1307.7454)

openalex publication_date 2015/01/08 · arxiv created 2015/04/21 · arxiv updated 2015/04/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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 ∈ R^{n × d} one row at a time. It performed O(d × ℓ) operations per row and maintains a sketch matrix B ∈ R^{ℓ × d} such that for any k < ℓ ‖A^TA - B^TB ‖₂ ≤ ‖A - A_k‖_F² / (ℓ-k) and ‖A - π_Bk(A)‖_F² ≤ (1 + (k)/(ℓ-k)) ‖A-A_k‖_F² . Here, A_k stands for the minimizer of ‖A - A_k‖_F over all rank k matrices (similarly B_k) and π_Bk(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.

Citations

• Finding frequent items in data streams
• Near-Optimal Column-Based Matrix Reconstruction
• Simple and Deterministic Matrix Sketching
• Relative Errors for Deterministic Low-Rank Matrix Approximations

Cited by

• A Simple, Optimal and Efficient Algorithm for Online Exp-Concave Optimization
• SAGE: Streaming Agreement-Driven Gradient Sketches for Representative Subset Selection
• Graph Coloring for Multi-Task Learning
• The Expiration Streaming Model: Diameter, k-Center, Counting, Sampling, and Friends
• Distribution-Aware Feature Selection for SAEs
• Co-Occuring Directions Sketching for Approximate Matrix Multiply
• Efficient Frequent Directions Algorithm for Sparse Matrices
• Continuous Subspace Optimization for Continual Learning

Related

• Simple and Deterministic Matrix Sketching
• Even Simpler Deterministic Matrix Sketching
• Efficient Frequent Directions Algorithm for Sparse Matrices
• Relative Errors for Deterministic Low-Rank Matrix Approximations
• Efficient Linear Bandits through Matrix Sketching