# Relative Errors for Deterministic Low-Rank Matrix Approximations

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Jul 2013.

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

- [Streaming Active Learning with Deep Neural Networks](https://mlsanity.com/paper/2303.02535/) (2023)
- [Even Simpler Deterministic Matrix Sketching](https://mlsanity.com/paper/2202.01780/) (2022)
- [Learning-Augmented Frequent Directions](https://mlsanity.com/paper/2503.00937/) (2025)
- [One-pass additive-error subset selection for ℓp subspace approximation](https://mlsanity.com/paper/2204.12073/) (2022)
- [On Subspace Approximation and Subset Selection in Fewer Passes by MCMC Sampling](https://mlsanity.com/paper/2103.11107/) (2021)

## Abstract (arXiv)

We consider processing an n x d matrix A in a stream with row-wise updates according to a recent algorithm called Frequent Directions (Liberty, KDD 2013). This algorithm maintains an l x d matrix Q deterministically, processing each row in O(d l^2) time; the processing time can be decreased to O(d l) with a slight modification in the algorithm and a constant increase in space. We show that if one sets l = k+ k/eps and returns Q_k, a k x d matrix that is the best rank k approximation to Q, then we achieve the following properties: ||A - A_k||_F^2 <= ||A||_F^2 - ||Q_k||_F^2 <= (1+eps) ||A - A_k||_F^2 and where pi_{Q_k}(A) is the projection of A onto the rowspace of Q_k then ||A - pi_{Q_k}(A)||_F^2 <= (1+eps) ||A - A_k||_F^2. We also show that Frequent Directions cannot be adapted to a sparse version in an obvious way that retains the l original rows of the matrix, as opposed to a linear combination or sketch of the rows.