# Tight Lower Bound for Linear Sketches of Moments

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Jun 2013.

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

- [p-Generalized Probit Regression and Scalable Maximum Likelihood Estimation via Sketching and Coresets](https://mlsanity.com/paper/2203.13568/) (2022)
- [Turnstile ℓp leverage score sampling with applications](https://mlsanity.com/paper/2406.00339/) (2024)

## Abstract (arXiv)

The problem of estimating frequency moments of a data stream has attracted a lot of attention since the onset of streaming algorithms [AMS99]. While the space complexity for approximately computing the prm th moment, for p∈(0,2] has been settled [KNW10], for p>2 the exact complexity remains open. For p>2 the current best algorithm uses O(n1-2/plog n) words of space [AKO11,BO10], whereas the lower bound is of Omega(n1-2/p) [BJKS04]. In this paper, we show a tight lower bound of Omega(n1-2/plog n) words for the class of algorithms based on linear sketches, which store only a sketch Ax of input vector x and some (possibly randomized) matrix A. We note that all known algorithms for this problem are linear sketches.