mlsanityData to 14 Oct 2026

Frequent Directions : Simple and Deterministic Matrix Sketching

arXiv 1501.01711 ↗First posted 8 Jan 2015cs.DScited by 39

Not on the map. Why?

Abstract (arXiv)

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 ∈ Rn × 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 < ℓ |ATA - BTB |2 ≤ |A - Ak|F2 / (ℓ-k) and |A - πBk(A)|F2 ≤ big(1 + frackℓ-kbig) |A-Ak|F2 . Here, Ak stands for the minimizer of |A - Ak|F over all rank k matrices (similarly Bk) and πBk(A) is the rank k matrix resulting from projecting A on the row span of Bk. 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.

Key facts. Cited by 39 papers in the map (data through 14 Oct 2026). First posted on arXiv 8 Jan 2015.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 12; 2022: 4; 2023: 4; 2024: 5; 2025: 7; 2026: 7.

39 papers.

Sort:

By area:

  1. 2021Multiplying Matrices Without Multiplyingcited by 30
  2. 2021MetaGrad: Adaptation using Multiple Learning Rates in Online Learningcited by 26
  3. 2021Learning to Forecast Dynamical Systems from Streaming Datacited by 17
  4. 2023Sketchy: Memory-efficient Adaptive Regularization with Frequent Directionscited by 17
  5. 2023Latent State Models of Training Dynamicscited by 16
  6. 2021EigenGame Unloaded: When playing games is better than optimizingcited by 13
  7. 2021Adversarial Robustness of Streaming Algorithms through Importance Samplingcited by 13
  8. 2025Streaming Attention Approximation via Discrepancy Theorycited by 11
  9. 2023Projection-free Online Exp-concave Optimizationcited by 10
  10. 2025Continuous Subspace Optimization for Continual Learningcited by 9
  11. 2024Revisiting Matrix Sketching in Linear Bandits: Achieving Sublinear Regret via Dyadic Block Sketchingcited by 4
  12. 2026Nearly Optimal Attention Coresetscited by 4
27 more
  1. 2023Sketching Multidimensional Time Series for Fast Discord Miningcited by 3
  2. 2024Optimal Matrix Sketching over Sliding Windowscited by 3
  3. 2025A Simple, Optimal and Efficient Algorithm for Online Exp-Concave Optimizationcited by 3
  4. 2021Sketching Merge Trees for Scientific Data Visualizationcited by 2
  5. 2021A Dimensionality Reduction Approach for Convolutional Neural Networkscited by 2
  6. 2024Spectral Guarantees for Adversarial Streaming PCAcited by 2
  7. 2025Learning-Augmented Frequent Directionscited by 2
  8. 2026Improved large-scale graph learning through ridge spectral sparsificationcited by 2
  9. 2021Effective Streaming Low-tubal-rank Tensor Approximation via Frequent Directionscited by 1
  10. 2021An Improved Frequent Directions Algorithm for Low-Rank Approximation via Block Krylov Iterationcited by 1
  11. 2022One-pass additive-error subset selection for ℓp subspace approximationcited by 1
  12. 2024Reweighted Solutions for Weighted Low Rank Approximationcited by 1
  13. 2025Graph Coloring for Multi-Task Learningcited by 1
  14. 2021On Subspace Approximation and Subset Selection in Fewer Passes by MCMC Samplingcited by 0
  15. 2021Speeding up PCA with primingcited by 0
  16. 2021QUINT: Node embedding using network hashingcited by 0
  17. 2022Improved analysis of randomized SVD for top-eigenvector approximationcited by 0
  18. 2022Non-Volatile Memory Accelerated Geometric Multi-Scale Resolution Analysiscited by 0
  19. 2022Scalable computation of prediction intervals for neural networks via matrix sketchingcited by 0
  20. 2024Learning nonnegative matrix factorizations from compressed datacited by 0
  21. 2025Distribution-Aware Feature Selection for SAEscited by 0
  22. 2025SAGE: Streaming Agreement-Driven Gradient Sketches for Representative Subset Selectioncited by 0
  23. 2026Scaling Federated Linear Contextual Bandits via Sketchingcited by 0
  24. 2026Accurate and Resource-Efficient Federated Continual Learningcited by 0
  25. 2026Efficient Multinomial Logistic Bandit via Frequent Directionscited by 0
  26. 2026Efficient Hypergradient Descent for Inverse Reinforcement Learningcited by 0
  27. 2026Efficient Linear Bandits via Cluster-Aware Sketchingcited by 0