# Why not solve s-sparse recovery on a stream by tracking moments?

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?

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).