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

CC BY-SA 4.0
2021-11-21T22:14:45.790Z
2021-11-21T22:14:45.790Z
mathworker21
<p>A slightly simplified version of <span class="math-container">$s$</span>-sparse recovery streaming problem is the following.  We get a stream of <span class="math-container">$n$</span> elements of the form <span class="math-container">$(x, \Delta)$</span>, where <span class="math-container">$x \in [u]$</span> is a member of the universe, and <span class="math-container">$\Delta \in \{-1, 1\}$</span> indicates whether this represents an instance of <span class="math-container">$x$</span> being added or removed from the pile.  We are promised that, in the end, at most <span class="math-container">$s$</span> universe elements have positive count in the pile and the rest have <span class="math-container">$0$</span>.  The goal is to return the list of surviving elements and their counts.</p>
<p>There is an elegant algorithm in <span class="math-container">$O(\log u \cdot \log n)$</span> space for <span class="math-container">$1$</span>-sparse recovery that works by tracking <span class="math-container">$w_0 := \sum_x f(x)$</span> (where <span class="math-container">$f(x)$</span> is the frequency of <span class="math-container">$x$</span> on the pile) and <span class="math-container">$w_1 := \sum_x x \cdot f(x)$</span>.  Then, in the end, the remaining element is <span class="math-container">$w_1/w_0$</span> and <span class="math-container">$w_0$</span> is its count.</p>
<p>In references that I've found by searching, <span class="math-container">$s$</span>-sparse recovery is typically solved by reduction to <span class="math-container">$1$</span>-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) <span class="math-container">$1$</span>-sparse recovery on each bucket separately.</p>
<p>To me, it seems natural to try to track the first <span class="math-container">$2s$</span> moments <span class="math-container">$\{w_i := \sum_x x^i \cdot f(x)\}$</span>, and then decode these moments appropriately into counts of the surviving elements.  If this works, it would use space <span class="math-container">$O(\log u \cdot \log n \cdot s)$</span>, comparable to the hashing strategy.  I'm curious why this does not seem popular:</p>
<blockquote>
<p>Is it true that one can uniquely decode the first <span class="math-container">$2s$</span> moments into the surviving frequency vector? If so, is there a simple/efficient algorithm to perform this decoding?</p>
</blockquote>
<p>Or is there some other reason to prefer the hashing strategy?</p>

<streaming-algorithms><compressed-sensing>
Why not solve s-sparse recovery on a stream by tracking moments?
GMB
# Why not solve s-sparse recovery on a stream by tracking moments?

(Asked by: username_0 on 2021-11-21)

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?

**Tags:** streaming-algorithms, compressed-sensing

---

## 1 answers

### Answer by username_1 on 2021-11-21. Score: 0

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


---

