# Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 27 references that are in the map.
- First posted on arXiv 16 Aug 2024.

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

- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Dimensionality Reduction for k-Means Clustering and Low Rank Approximation](https://mlsanity.com/paper/1410.6801/) (2014)
- [Projection-Cost-Preserving Sketches: Proof Strategies and Constructions](https://mlsanity.com/paper/2004.08434/) (2020)
- [Tight Bounds for Sketching the Operator Norm, Schatten Norms, and Subspace Embeddings](https://mlsanity.com/paper/2202.09797/) (2022)
- [High Probability Frequency Moment Sketches](https://mlsanity.com/paper/1805.10885/) (2018)

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

- [Learning-Augmented Frequent Directions](https://mlsanity.com/paper/2503.00937/) (2025)

## Abstract (arXiv)

We study the problem of residual error estimation for matrix and vector norms using a linear sketch. Such estimates can be used, for example, to quickly assess how useful a more expensive low-rank approximation computation will be. The matrix case concerns the Frobenius norm and the task is to approximate the k-residual |A - Ak|F of the input matrix A within a (1+ε)-factor, where Ak is the optimal rank-k approximation. We provide a tight bound of Theta(k2/ε4) on the size of bilinear sketches, which have the form of a matrix product SAT. This improves the previous O(k2/ε6) upper bound in (Andoni et al. SODA 2013) and gives the first non-trivial lower bound, to the best of our knowledge. In our algorithm, our sketching matrices S and T can both be sparse matrices, allowing for a very fast update time. We demonstrate that this gives a substantial advantage empirically, for roughly the same sketch size and accuracy as in previous work. For the vector case, we consider the ℓp-norm for p>2, where the task is to approximate the k-residual |x - xk|p up to a constant factor, where xk is the optimal k-sparse approximation to x. Such vector norms are frequently studied in the data stream literature and are useful for finding frequent items or so-called heavy hitters. We establish an upper bound of O(k2/pn1-2/poperatornamepoly(log n)) for constant ε on the dimension of a linear sketch for this problem. Our algorithm can be extended to the ℓp sparse recovery problem with the same sketching dimension, which seems to be the first such bound for p > 2. We also show an Omega(k2/pn1-2/p) lower bound for the sparse recovery problem, which is tight up to a poly(log n) factor.