# Frequent Directions : Simple and Deterministic Matrix Sketching

arXiv: https://arxiv.org/abs/1501.01711 · HTML: https://mlsanity.com/paper/1501.01711/

## Key facts

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

## Built on by (most cited first, 30 of 39)

- [Multiplying Matrices Without Multiplying](https://mlsanity.com/paper/2106.10860/) (2021)
- [MetaGrad: Adaptation using Multiple Learning Rates in Online Learning](https://mlsanity.com/paper/2102.06622/) (2021)
- [Learning to Forecast Dynamical Systems from Streaming Data](https://mlsanity.com/paper/2109.09703/) (2021)
- [Sketchy: Memory-efficient Adaptive Regularization with Frequent Directions](https://mlsanity.com/paper/2302.03764/) (2023)
- [Latent State Models of Training Dynamics](https://mlsanity.com/paper/2308.09543/) (2023)
- [EigenGame Unloaded: When playing games is better than optimizing](https://mlsanity.com/paper/2102.04152/) (2021)
- [Adversarial Robustness of Streaming Algorithms through Importance Sampling](https://mlsanity.com/paper/2106.14952/) (2021)
- [Streaming Attention Approximation via Discrepancy Theory](https://mlsanity.com/paper/2502.07861/) (2025)
- [Projection-free Online Exp-concave Optimization](https://mlsanity.com/paper/2302.04859/) (2023)
- [Continuous Subspace Optimization for Continual Learning](https://mlsanity.com/paper/2505.11816/) (2025)
- [Revisiting Matrix Sketching in Linear Bandits: Achieving Sublinear Regret via Dyadic Block Sketching](https://mlsanity.com/paper/2410.10258/) (2024)
- [Nearly Optimal Attention Coresets](https://mlsanity.com/paper/2605.05602/) (2026)
- [Sketching Multidimensional Time Series for Fast Discord Mining](https://mlsanity.com/paper/2311.03393/) (2023)
- [Optimal Matrix Sketching over Sliding Windows](https://mlsanity.com/paper/2405.07792/) (2024)
- [A Simple, Optimal and Efficient Algorithm for Online Exp-Concave Optimization](https://mlsanity.com/paper/2512.23190/) (2025)
- [Sketching Merge Trees for Scientific Data Visualization](https://mlsanity.com/paper/2101.03196/) (2021)
- [A Dimensionality Reduction Approach for Convolutional Neural Networks](https://mlsanity.com/paper/2110.09163/) (2021)
- [Spectral Guarantees for Adversarial Streaming PCA](https://mlsanity.com/paper/2408.10332/) (2024)
- [Learning-Augmented Frequent Directions](https://mlsanity.com/paper/2503.00937/) (2025)
- [Improved large-scale graph learning through ridge spectral sparsification](https://mlsanity.com/paper/2604.20078/) (2026)
- [Effective Streaming Low-tubal-rank Tensor Approximation via Frequent Directions](https://mlsanity.com/paper/2108.10129/) (2021)
- [An Improved Frequent Directions Algorithm for Low-Rank Approximation via Block Krylov Iteration](https://mlsanity.com/paper/2109.11703/) (2021)
- [One-pass additive-error subset selection for ℓp subspace approximation](https://mlsanity.com/paper/2204.12073/) (2022)
- [Reweighted Solutions for Weighted Low Rank Approximation](https://mlsanity.com/paper/2406.02431/) (2024)
- [Graph Coloring for Multi-Task Learning](https://mlsanity.com/paper/2509.16959/) (2025)
- [On Subspace Approximation and Subset Selection in Fewer Passes by MCMC Sampling](https://mlsanity.com/paper/2103.11107/) (2021)
- [Speeding up PCA with priming](https://mlsanity.com/paper/2109.03709/) (2021)
- [QUINT: Node embedding using network hashing](https://mlsanity.com/paper/2109.04206/) (2021)
- [Improved analysis of randomized SVD for top-eigenvector approximation](https://mlsanity.com/paper/2202.07992/) (2022)
- [Non-Volatile Memory Accelerated Geometric Multi-Scale Resolution Analysis](https://mlsanity.com/paper/2202.11518/) (2022)

## 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.