Sparse Recovery with Count-Sketch

Background

A stream of items $S = \{ a_1, a_2, ..., a_m \}$ where $a_i \in [n]$. Let the frequencies of elements in $[n]$ be $f = \left< f_1, f_2, ..., f_n \right>$, where $f_j = |\{ a_i \in S : a_i = j \}|$.

Count-Sketch

It returns an estimation $\hat f$ of $f$ with space $O(\frac{1}{\epsilon^2} \log n)$ words, such that with probability at least $1 - 1 / n$, for every $i \in [n]$,

where $\Vert f \Vert_2 = \sqrt {\sum_{i = 1}^n f_i^2 }$.

Problem

In general, a sketch is a concise representation of $f$. Suppose that we limit our space usage to $k$ words (i.e., $\Vert \hat f \Vert_0 = k$). Then the sketch $\hat f$ that minimizes the $\ell_2$ error

keeps the set $H$ of $k$ items with highest frequencies. In such case, the error is given by

In practice, however, $S$ is not given offline. As we don't know $H$, we can only compute an $\hat f$ with $k$ words that is as good as possible. The question is, how far $\Vert f - \hat f \Vert_2$ can be from the minimum possible value, namely $err_2^k(f)$?

Algorithm

One possible solution, proposed by Cormode and Muthukrishnan [1], is to construct $\hat f$ vis Count-Sketch. In particular,

1. It uses $d = O(\log n)$ hash tables.
2. Each hash table has size $w = \frac{3k}{\epsilon^2}$.

Frequency Oracle Error

Lemma 1. For every $i \in [n]$, with probability $1 - 1 /n^2$,

$$|f_i - \hat f_i| \le \frac{\epsilon}{\sqrt k } err_2^k(f).$$

Remark: If $f$ is $k$ sparse, i.e., the number of non-zero elements of $f$ is at most $k$, then $err_2^k(f) = 0$ and the algorithm recovers $f$ exactly.

Proof: Consider a fixed $t \in [k]$. For $i \in [n]$, let $h_t(i)$ the bucket of item $i$ in the $t$-th hash table. Define

be the event such that some heavy item collides with $i$ in the $t$-th table. Then by union bound,

Therefore, by the law of total probability and monotonicity of probability, we have

As long as $\epsilon^2 / 3 < 1 / 6$, this probability is smaller than $1 / 2$. We can boost the failure probability to $1/ n^2$ by repeating the hash tables $d = O(\log n)$ times and taking the median as estimation.

$\blacksquare$

Sparse Vector Construction

The next step is keep only set $\hat H$ of the $k$ largest items in $\hat f$. Note that $\hat H$ might not equals to $H$. To bound the value $\Vert f - \hat f \Vert_2$, we partition $[n]$ into three parts:

Lemma 2. $\sum_{i \in \hat H} (f_i - \hat f_i)^2 \le \epsilon^2 (err_2^k(f))^2$.

Proof. By lemma 1, each term $(f_i - \hat f_i)^2$ has error at most $\frac{\epsilon^2}{k} (err_2^k(f))^2$. The claim then follows from that $|\hat H| = k$.

$\blacksquare$

Lemma 3. $\sum_{i \in H \setminus \hat H} f_i ^2 \le \sum_{j \in \hat H \setminus H} \hat f_j^2 + (2 \epsilon + \epsilon^2) ( err_2^k(f))^2$

Proof. $|H| = |\hat H|$, we have $|H \setminus \hat H| = |\hat H \setminus H|$.

If $H \setminus \hat H = \emptyset$, the claim is trivial. Otherwise, we can construct a bijection between $H \setminus \hat H$ and $\hat H \setminus H$. Then for $i \in H \setminus \hat H$, let $j$ be its corresponding index in $\hat H \setminus H$. Then

Therefore,

and

$\square$

Reference

[1] G. Cormode and S. Muthukrishnan. Combinatorial algorithms for Compressed Sensing.
[2] Moses Charikar, Lecture 9, CS 369G: Algorithmic Techniques for Big Data