Linear Sketches and Recovering Sparse Signals from Bucket Measurements

Every sketch discussed so far is a linear map: a fixed matrix $A$ of size $r \times m$ applied to the frequency vector $x$, maintained incrementally as $y \leftarrow y + A e_i$ for each stream update. The map compresses $m$ dimensions into $r$, and the estimator that reads $y$ is a decoder. For a sum or a norm, decoding is arithmetic on the whole array. For a question about which items are heavy, decoding has to identify indices, and that is a harder problem: the matrix has destroyed the coordinate structure that made the answer obvious.

Recovering sparse structure from $r \ll m$ measurements is the subject of compressed sensing, and the streaming versions are its algorithmic core. The interesting part is not that recovery is possible — it is that recovery is possible with a matrix whose columns are far from orthogonal, provided the signal is sparse enough and the decoder uses the right rule.

The measurement model and what “sparse” buys

Write $x \in \mathbb{R}^m$ for the frequency vector, and suppose it has at most $s$ non-zero entries. The sketch is $y = Ax$ with $A$ an $r \times m$ matrix. Recovering $x$ from $y$ is solving an underdetermined linear system: $r$ equations, $m$ unknowns, and infinitely many solutions unless a prior is imposed. The prior is sparsity.

For a general matrix the problem is hopeless: the null space of $A$ has dimension at least $m - r$, and any solution can be perturbed by a null-space vector to produce another solution with the same measurements. Sparsity helps only if the null space contains no sparse vectors — that is, if no vector with $s$ or fewer non-zeros lies in $\ker A$. That condition is what the restricted isometry property (RIP) formalises.

$A$ satisfies $(s, \delta)$-RIP if for every $s$-sparse vector $v$,

$$ (1 - \delta)|v|_2^2 ;\leq; |Av|_2^2 ;\leq; (1 + \delta)|v|_2^2 $$

A matrix with this property preserves the geometry of sparse vectors: it is close to an isometry on every $s$-dimensional coordinate subspace. Random matrices satisfy RIP with high probability when $r = O(s \log(m/s))$, and the logarithm is not an artefact of the proof: an $s$-sparse vector is specified by its support and its values, and choosing a support of size $s$ out of $m$ already costs $s \log(m/s)$ bits by a counting argument, which bounds the number of measurements from below as well.

For a streaming sketch the matrix is chosen so that $Ax$ can be updated in $O(1)$ time per element, which rules out dense Gaussian matrices — multiplying by a dense matrix costs $O(r)$ per update. The usual choice is a sparse random matrix with a small number of non-zeros per column, or a structured matrix whose product with a basis vector can be computed from a hash. Both families satisfy RIP-like conditions, with slightly worse constants.

Bucket sums, and why one row cannot identify anything

The Count-Sketch construction uses $d$ rows of $w$ buckets. Each row has a hash $h_r: [m] \to [w]$ and a sign function $\sigma_r: [m] \to {-1, +1}$, and an update of item $i$ by $\Delta$ adds $\sigma_r(i)\Delta$ to bucket $h_r(i)$ of row $r$. The measurement in bucket $j$ of row $r$ is

$$ y_{r,j} = \sum_{i : h_r(i) = j} \sigma_r(i) x_i $$

The signs are the crucial difference from Count-Min. Without them, a bucket is a sum of non-negative values and a colliding item can only inflate it. With them, colliding items cancel in expectation, so the bucket value is an unbiased estimate of the queried item’s frequency up to the sign:

$$ \mathbb{E}[\sigma_r(i) , y_{r, h_r(i)}] = x_i $$

and the deviation is the signed sum of the other items in the bucket, whose variance is proportional to the $\ell_2$ norm of those items rather than their $\ell_1$ sum. For a skewed vector — the case that matters — the $\ell_2$ norm of the tail is much smaller than its $\ell_1$ mass, so the per-bucket noise is much lower than Count-Min’s.

Taking the median across $d$ rows gives an estimate whose error exceeds a threshold with probability exponentially small in $d$. The median is what makes identification work: a single row’s bucket value can be dominated by one large colliding item, but a majority of rows will not be, so the median recovers the true value.

import hashlib

def make_row(key, row, width, seed):
    h = hashlib.blake2b(key + row.to_bytes(2, 'big') + seed, digest_size=8).digest()
    v = int.from_bytes(h, 'big')
    bucket = v % width
    sign = 1 if (v >> 63) & 1 else -1     # independent bit for the sign
    return bucket, sign

def estimate(rows, key, width, seed):
    vals = []
    for r, row in enumerate(rows):
        b, s = make_row(key, r, width, seed)
        vals.append(s * row[b])
    vals.sort()
    return vals[len(vals) // 2]

Deriving the sign from a different bit of the same hash is a convenience; the analysis wants the sign to be independent of the bucket index, and a hash whose high bits are independent of its low bits supplies that in practice. Using the low bit of the bucket index as the sign would correlate the two and break the cancellation argument, since colliding items would then systematically share signs.

From estimates to identities: the heavy hitter loop

Estimating a known item’s frequency is not the same as finding unknown heavy items. The sketch stores bucket sums; nothing in it enumerates keys. The recovery procedure has to search the key space, and the standard search is a loop over buckets.

If item $i$ has frequency above a threshold, then in every row it lands in a bucket whose value is dominated by $i$. Scanning all buckets of one row and taking the largest values yields a candidate set containing every heavy item, together with many false candidates produced by bucket collisions. For each candidate, compute its median estimate and keep those above the threshold. The false candidates fail the second test because a bucket’s large value is not reproducible across rows for an item that is not actually heavy.

The cost is $O(dw)$ work per recovery — one pass over the sketch — plus $O(d)$ per candidate. That is fine when the sketch is small and recovery is rare. It is not fine when recovery happens per query, which is why point queries and heavy-hitter enumeration are different operations on the same structure, with very different costs.

The loop’s correctness rests on a threshold argument. If the sketch is built with width $w = O(1/\varepsilon)$ and depth $d = O(\log(1/\delta))$, then every item with $x_i > \varepsilon |x|_2$ appears in the candidate set with probability $1 - \delta$, and every reported item has true frequency within $\varepsilon |x|_2$ of its estimate. The norm in the bound is $\ell_2$, not $\ell_1$; this is the improvement over Count-Min and it is why the sign is worth the extra work.

What the recovery cannot do below the threshold

The threshold is the whole story. An item whose frequency is a small fraction of the $\ell_2$ norm is indistinguishable from noise, and no amount of post-processing recovers it, because the information is not in $y$.

This is not a failure of the algorithm; it is a consequence of $r < m$. The sketch has $r$ numbers and the vector has $m$, and the RIP bound says that $r = \Omega(s \log(m/s))$ is necessary to recover an $s$-sparse vector. To recover an item of frequency $\phi |x|_2$ requires $r = \Omega((1/\phi) \log m)$ measurements, which for small $\phi$ approaches $m$. The sketch stops being a compression at that point.

The turnstile case is harder still. With signed updates, an item’s frequency can be zero at query time even though it was large earlier, and the sketch cannot distinguish “never present” from “present and cancelled”. Recovery in the turnstile model needs the $\ell_1$ norm of the residual rather than $\ell_2$, and the achievable bounds are worse. The $\ell_0$-sampling primitive — returning a uniformly random non-zero coordinate of the residual — is the building block for turnstile recovery, at a cost of $O(\log^2 m)$ bits of state per sample, which is why full turnstile sparse recovery is expensive even though it is possible in principle.

The gap between theory and an implementation

Three practical matters separate a sketch that satisfies RIP from one that works.

The decoder matters as much as the matrix. The theoretical decoder solves a linear program — minimise $|x|_1$ subject to $Ax = y$ — which for a streaming sketch is far more expensive than maintaining the sketch. Greedy decoders (orthogonal matching pursuit, iterative hard thresholding) are cheaper but need stronger RIP constants. The bucket-scan-and-median decoder described above is the cheapest of all and gets the weakest guarantees; it is the one that fits a stream, and it is why the practical bounds are stated in terms of $\ell_2$ mass rather than exact recovery.

Sparsity assumptions are about the residual, not the signal. A stream with a million distinct keys and a thousand heavy ones is not sparse, but its residual after removing the heavy hitters is. The recovery loop runs iteratively: find a heavy hitter, subtract its contribution from the sketch, and repeat. Each iteration needs the sketch to support subtracting a known item’s contribution, which linearity provides exactly. The number of iterations is bounded by the number of heavy items, and each iteration costs a scan.

Hash collisions are adversarial under a fixed seed. The RIP guarantee is over the random choice of matrix. A sketch built with a fixed seed and exposed to inputs designed against that seed has no guarantee at all. Randomising the seed per instance is the only defence, and it must be done at sketch creation, not at query time.

Where linear sketches sit among the alternatives

A linear sketch is the only summary that supports both estimation and merging with exact semantics, and the price is that every query must be expressible as a linear functional of $y$. Non-linear summaries — the counters in Misra-Gries, the buckets in exponential histograms — can answer questions that linear sketches cannot, at the cost of mergeability.

The choice between Count-Sketch-style recovery and Count-Min comes down to the norm in the error bound. If the stream’s tail is heavy — many items of moderate frequency — the $\ell_1$ bound of Count-Min is loose and the $\ell_2$ bound of Count Sketch is much tighter. If the stream is dominated by one item, the two bounds are within a constant factor and Count-Min’s simpler update wins. If updates can be negative, only the signed construction is valid, since Count-Min’s minimum over non-negative counters becomes meaningless under subtraction.

The deeper lesson is that compression and identifiability trade against each other in a way that the space bound alone hides. A sketch of $r$ measurements can answer any linear functional to precision governed by $r$, but it can only name items whose mass is a $1/r$ fraction of the norm. Queries that need names are fundamentally more expensive than queries that need numbers, and the difference is the $\log(m/s)$ factor in the measurement count.