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

Question

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?

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