Sparse Recovery from Count-Sketch Measurements

Recovering Spikes from Hashed Measurements

Suppose a long signal (x\in\mathbb R^n) contains a few large coordinates and a diffuse background. Storing every coordinate is like giving every musician a separate microphone; Count-Sketch instead routes many musicians into a small set of channels, flips each contribution by a reproducible random sign, and repeats the mixing several times. A loud soloist can then be estimated from channels in which the other sounds mostly cancel.

For row (r), choose a bucket hash (h_r:[n]\to[b]) and a sign hash (s_r:[n]\to\{-1,+1\}). The stored counter is \[ C_{r,t}=\sum_{j:h_r(j)=t}s_r(j)x_j. \] An update ((j,\Delta)) adds (s_r(j)\Delta) to bucket (h_r(j)) in every row. The point estimate for coordinate (i) is \[ \widetilde x_i=\operatorname{median}_{r\in[d]}\bigl(s_r(i)C_{r,h_r(i)}\bigr). \] In one row this equals (x_i+\sum_{j\ne i:h_r(j)=h_r(i)}s_r(i)s_r(j)x_j): the target plus signed collision noise.

For example, let (x=(0,9,1,0,-2,0)). If a row sends coordinate 2 to a bucket with coordinate 5, using signs (s(2)=+1,s(5)=-1), that counter is (9+2=11), so the row estimates (11), not (9). Other independent rows create different collisions; the median resists the minority of contaminated estimates.

The support contains nonzero coordinates. A vector is (k)-sparse when at most (k) coordinates are nonzero. Its best (k)-term approximation (x_k) retains the (k) largest magnitudes, and the tail energy is \(\lVert x-x_k\rVert_2^2\). Isolation means a heavy coordinate shares no bucket with the other chosen heavy coordinates in a row. Candidate generation produces a small set worth querying; a Count-Sketch point-query structure alone does not reveal names without scanning the universe. An \(\ell_2/\ell_2\) recovery returns a sparse (\widehat x) whose residual energy is close to the optimal tail energy.

This fills the gap between the earlier Count-Min-versus-Count-Sketch comparison and an actual decoder. Signed counters remove Count-Min's one-sided bias, but a useful recovery pipeline still needs enough buckets for low noise, enough rows for confidence, and a defensible way to enumerate candidates.

Isolation and Median Coordinate Estimates

Fix a coordinate (i) and let (H) contain the (k) largest-magnitude coordinates other than (i). In a row, split the error (Z_r=\widetilde x_i^{(r)}-x_i) into heavy and tail collisions. With (b\ge 4k), a union bound gives \[ \Pr[\exists j\in H:h_r(j)=h_r(i)]\le k/b\le1/4. \] Thus (i) is isolated from (H) with probability at least (3/4).

Conditioned on the bucket hashes, pairwise-independent zero-mean signs cancel cross terms. For the remaining tail (T=[n]\setminus(H\cup\{i\})), \[ \mathbb E[Z_r^2]=\sum_{j\in T}\Pr[h_r(j)=h_r(i)]x_j^2 \le \frac{\lVert x_T\rVert_2^2}{b}. \] Markov's inequality applied to (Z_r^2) implies a constant-probability bound (\lvert Z_r\rvert\le c\lVert x_T\rVert_2/\sqrt b) for an explicit constant (c). Combining the isolation and tail-noise events leaves a constant probability that one row is good. If rows are independent and (d=\Theta(\log(n/\delta))), a Chernoff bound makes the median good for all (n) queried coordinates with probability at least (1-\delta).

Setting (b=\Theta(k/\varepsilon^2)) yields the familiar simultaneous point-error scale \[ \lvert\widetilde x_i-x_i\rvert\le O\!\left(\frac{\varepsilon}{\sqrt{k}}\lVert x-x_k\rVert_2\right). \] The exact constant depends on the hash independence and the allocation of failure probability. The proof obligation is not merely “the median is robust”: one must establish a per-row good-event probability strictly above (1/2), independence across rows, then union-bound over every coordinate actually queried.

There are important boundaries. With no random signs, positive collisions introduce Count-Min-style bias. With (b\ll k), heavy-heavy collisions occur too often. Pairwise independence is enough for the second-moment calculation but not automatically for every adaptive or high-probability claim. If an adversary chooses updates after learning the hashes, it can engineer collisions. Count-Sketch also differs from an expander-based identification sketch: the latter encodes enough neighbor structure or messages to recover coordinate identities without scanning all (n).

flowchart TD
    A[Linear signed bucket counters] --> B[Fix coordinate i and one row]
    B --> C[Separate heavy set H from tail T]
    C --> D[Enough buckets isolate i from H]
    C --> E[Random signs give zero-mean tail noise]
    E --> F[Second moment bounds tail error]
    D --> G[One row is good with probability above one half]
    F --> G
    G --> H[Independent rows and median amplification]
    H --> I[Simultaneous point estimates]
    I --> J[Candidate selection plus pruning]
    J --> K[l2 over l2 sparse recovery]
    C --> L{Too few buckets or exposed hashes?}
    L -->|yes| M[Isolation or concentration can fail]
    L -->|no| D
    classDef navy fill:#17365D,color:#fff,stroke:#17365D;
    classDef teal fill:#147D84,color:#fff,stroke:#0D565B;
    classDef purple fill:#6C3BAA,color:#fff,stroke:#472675;
    classDef crimson fill:#C6284D,color:#fff,stroke:#861B35;
    class A,B,C navy;
    class D,E,F,G,H purple;
    class I,J,K teal;
    class L,M crimson;

From Point Error to Sparse Recovery

Assume estimates obey (\lvert\widetilde x_i-x_i\rvert\le\eta) simultaneously. If all coordinates can be queried, form (S), the indices of the largest (k) values of (\lvert\widetilde x_i\rvert), and output (\widehat x_i=\widetilde x_i) for (i\in S), zero otherwise. The selection argument pairs any missed true top-(k) coordinate with a selected outsider having at least as large an estimated magnitude. Triangle inequalities charge the swap to estimation error and tail energy. A sufficiently smaller point-error constant—normally obtained by sizing buckets with the desired recovery accuracy—yields \[ \lVert x-\widehat x\rVert_2\le(1+O(\varepsilon))\lVert x-x_k\rVert_2. \] Thresholding often keeps (O(k)), rather than exactly (k), candidates before a final pruning step. That slack prevents near-ties around rank (k) from causing a brittle proof.

The guarantee is relative to the best (k)-term approximation, not exact coordinate recovery. When (x) is exactly (k)-sparse, the tail is zero and the ideal theorem forces exact recovery, but only under arithmetic and identification assumptions strong enough to realize the zero-error conclusion. Floating-point counters, quantization, finite fields, and imperfect candidate lists add separate error terms.

from hashlib import blake2b
from math import sqrt

def hash_u64(seed, row, domain, key):
    data = f"{seed}|{row}|{domain}|{key}".encode()
    return int.from_bytes(blake2b(data, digest_size=8, person=b"cs-demo-v1").digest(), "big")

class CountSketch:
    def __init__(self, universe, buckets, rows, seed=17):
        if min(universe, buckets, rows) <= 0:
            raise ValueError("universe, buckets, and rows must be positive")
        self.n, self.b, self.d, self.seed = universe, buckets, rows, seed
        self.counters = [[0.0] * buckets for _ in range(rows)]

    def _bucket(self, row, key):
        return hash_u64(self.seed, row, "bucket", key) % self.b

    def _sign(self, row, key):
        return 1 if hash_u64(self.seed, row, "sign", key) & 1 else -1

    def update(self, key, delta):
        if not 0 <= key < self.n:
            raise ValueError("key outside universe")
        for row in range(self.d):
            self.counters[row][self._bucket(row, key)] += self._sign(row, key) * delta

    def estimate(self, key):
        if not 0 <= key < self.n:
            raise ValueError("key outside universe")
        values = [self._sign(r, key) * self.counters[r][self._bucket(r, key)]
                  for r in range(self.d)]
        values.sort()
        m = len(values) // 2
        return values[m] if len(values) % 2 else (values[m - 1] + values[m]) / 2

    def recover_by_scan(self, k):
        if not 1 <= k <= self.n:
            raise ValueError("k must lie in [1, universe]")
        estimates = [self.estimate(i) for i in range(self.n)]
        support = sorted(range(self.n), key=lambda i: (-abs(estimates[i]), i))[:k]
        return {i: estimates[i] for i in support}

def residual_norm(vector, recovered):
    return sqrt(sum((value - recovered.get(i, 0.0)) ** 2
                    for i, value in enumerate(vector)))

def best_k_error(vector, k):
    keep = set(sorted(range(len(vector)), key=lambda i: -abs(vector[i]))[:k])
    return sqrt(sum(value * value for i, value in enumerate(vector) if i not in keep))

signal = [0, 10, 0, -7, 2, 1, -1, 0, 0, 0, 0, 0]
sketch = CountSketch(len(signal), buckets=32, rows=9, seed=23)
for index, value in enumerate(signal):
    if value:
        sketch.update(index, value)
recovered = sketch.recover_by_scan(2)
assert set(recovered) == {1, 3}
assert residual_norm(signal, recovered) <= best_k_error(signal, 2) + 1e-12

sketch.update(1, -10)
assert abs(sketch.estimate(1)) < 1e-12
after_delete = sketch.recover_by_scan(2)
assert 3 in after_delete

empty = CountSketch(8, buckets=8, rows=5)
assert all(empty.estimate(i) == 0 for i in range(8))

try:
    empty.update(8, 1)
    raise AssertionError("invalid key accepted")
except ValueError:
    pass

collision_heavy = CountSketch(12, buckets=1, rows=5, seed=23)
for index, value in enumerate(signal):
    if value:
        collision_heavy.update(index, value)
assert any(abs(collision_heavy.estimate(i) - signal[i]) > 0 for i in range(len(signal)))

print("recovered:", recovered)
print("best-k error:", best_k_error(signal, 2), "residual:", residual_norm(signal, recovered))
print("after deletion:", after_delete)

Sparse Signals in Telemetry and Science

In a teaching case, use (n=64), plant three spikes, add bounded random tail noise, then compare every point estimate and the recovered top three against the exact vector. Vary buckets while holding the signal fixed: collision error should fall statistically, not monotonically on every seed.

In professional telemetry, coordinates may be service-error signatures or endpoint/status-code pairs. Updates can be positive and negative when late corrections arrive, making signed linear sketches attractive. Candidate generation might come from a bounded service catalog, a separate heavy-hitter identifier, or periodic dictionary snapshots. Choose (k) from the incident budget, size (b) from the tolerated tail error, size (d) from the number of queried candidates and failure budget, and version all hash seeds so distributed sketches remain merge-compatible.

In science, coordinates may be spectral bins or genomic features. Recovery is defensible when the signal is compressible in the chosen basis and measurement noise fits the error model. It is not defensible when important structure is dense, when “large” coordinates are scientifically biased by preprocessing, or when an adaptive party can learn the hash functions and construct collisions.

Evidence that invalidates deployment includes a tail norm far above the design range, false-negative rates concentrated near operational thresholds, residual ratios exceeding the promised tolerance on exact audits, row estimates with persistent same-direction bias, incompatible seeds across shards, arithmetic saturation, or decode time dominated by a supposedly impossible full-universe scan.

flowchart TD
    A[Define sparse objective and coordinate basis] --> B[Measure k tail energy and query volume]
    B --> C{Candidate identities available?}
    C -->|yes| D[Size buckets rows and counters]
    C -->|no| E[Add identification structure or reject]
    D --> F[Validate against exact held-out streams]
    F --> G{Point error residual and recall pass?}
    G -->|yes| H[Deploy versioned merge-compatible sketches]
    G -->|no| I[Resize change model or reject]
    H --> J[Monitor tail drift saturation and seed exposure]
    J --> K{Assumptions still valid?}
    K -->|yes| J
    K -->|no| I
    classDef navy fill:#17365D,color:#fff,stroke:#17365D;
    classDef teal fill:#147D84,color:#fff,stroke:#0D565B;
    classDef purple fill:#6C3BAA,color:#fff,stroke:#472675;
    classDef crimson fill:#C6284D,color:#fff,stroke:#861B35;
    class A,B,C navy;
    class D,F purple;
    class G,H,J teal;
    class E,I,K crimson;

Reconstruct and Verify a Sparse Vector

Complete the following stages in order. Keep the exact vector beside the sketch during development; a recovery theorem is not a substitute for an oracle on controlled tests.