# Optimal Matrix Sketching over Sliding Windows

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 40 references that are in the map.
- First posted on arXiv 13 May 2024.

## Builds on (most cited first, 6 of 6)

- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decomposition](https://mlsanity.com/paper/1504.05477/) (2015)
- [Frequent Directions : Simple and Deterministic Matrix Sketching](https://mlsanity.com/paper/1501.01711/) (2015)
- [Near Optimal Linear Algebra in the Online and Sliding Window Models](https://mlsanity.com/paper/1805.03765/) (2018)
- [Learnability with Time-Sharing Computational Resource Concerns](https://mlsanity.com/paper/2305.02217/) (2023)
- [Ridge Regression with Frequent Directions: Statistical and Optimization Perspectives](https://mlsanity.com/paper/2011.03607/) (2020)

## Built on by (most cited first, 3 of 3)

- [Revisiting Matrix Sketching in Linear Bandits: Achieving Sublinear Regret via Dyadic Block Sketching](https://mlsanity.com/paper/2410.10258/) (2024)
- [Optimal Approximate Matrix Multiplication over Sliding Windows](https://mlsanity.com/paper/2502.18830/) (2025)
- [Mutable Low-Rank Sketches for Retrain-Free Recommendation](https://mlsanity.com/paper/2607.15242/) (2026)

## Abstract (arXiv)

Matrix sketching, aimed at approximating a matrix boldsymbolA ∈ ℝN× d consisting of vector streams of length N with a smaller sketching matrix boldsymbolB ∈ ℝℓ× d, ℓ ll N, has garnered increasing attention in fields such as large-scale data analytics and machine learning. A well-known deterministic matrix sketching method is the Frequent Directions algorithm, which achieves the optimal Oleft(fracdvarepsilonright) space bound and provides a covariance error guarantee of varepsilon = lVert boldsymbolA^top boldsymbolA - boldsymbolB^top boldsymbolB rVert2/lVert boldsymbolA rVertF2. The matrix sketching problem becomes particularly interesting in the context of sliding windows, where the goal is to approximate the matrix boldsymbolAW, formed by input vectors over the most recent N time units. However, despite recent efforts, whether achieving the optimal Oleft(fracdvarepsilonright) space bound on sliding windows is possible has remained an open question. In this paper, we introduce the DS-FD algorithm, which achieves the optimal Oleft(fracdvarepsilonright) space bound for matrix sketching over row-normalized, sequence-based sliding windows. We also present matching upper and lower space bounds for time-based and unnormalized sliding windows, demonstrating the generality and optimality of dsfd across various sliding window models. This conclusively answers the open question regarding the optimal space bound for matrix sketching over sliding windows. Furthermore, we conduct extensive experiments with both synthetic and real-world datasets, validating our theoretical claims and thus confirming the correctness and effectiveness of our algorithm, both theoretically and empirically.