A slightly simplified version of $s$-sparse recovery streaming problem is the following. We get a stream of $n$ elements of the form $(x, \Delta)$, where $x \in [u]$ is a member of the universe, and $\Delta \in \{-1, 1\}$ indicates whether this represents an instance of $x$ being added or removed from the pile. We are promised that, in the end, at most $s$ universe elements have positive count in the pile and the rest have $0$. The goal is to return the list of surviving elements and their counts.

There is an elegant algorithm in $O(\log u \cdot \log n)$ space for $1$-sparse recovery that works by tracking $w_0 := \sum_x f(x)$ (where $f(x)$ is the frequency of $x$ on the pile) and $w_1 := \sum_x x \cdot f(x)$. Then, in the end, the remaining element is $w_1/w_0$ and $w_0$ is its count.

In references that I've found by searching, $s$-sparse recovery is typically solved by reduction to $1$-sparse recovery, roughly by hashing the stream, arguing that a hash with appropriate parameters puts most surviving elements in a bucket by themselves with high probability, and then solving (a slightly stronger, promise-less version of) $1$-sparse recovery on each bucket separately.

To me, it seems natural to try to track the first $2s$ moments $\{w_i := \sum_x x^i \cdot f(x)\}$, and then decode these moments appropriately into counts of the surviving elements. If this works, it would use space $O(\log u \cdot \log n \cdot s)$, comparable to the hashing strategy. I'm curious why this does not seem popular:

Is it true that one can uniquely decode the first $2s$ moments into the surviving frequency vector? If so, is there a simple/efficient algorithm to perform this decoding?

Or is there some other reason to prefer the hashing strategy?


1 Answer 1


If $\sum_{k=1}^s c_k a_k^i = \sum_{k=1}^s d_k b_k^i$ for $0 \le i \le 2s-1$, then $\sum_{k=1}^{2s} r_k x_k^i = 0$ for $0 \le i \le 2s-1$, where $r_k$ is $c_k$ or $-d_k$ and $x_k$ is $a_k$ or $b_k$. In other words $(x_k^i)_{i,k}\vec{r} = \vec{0}$ but Vandermonde matrix is invertible (if some $a_k$ is equal to some $b_{k'}$, then just combine them and remove a moment).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.