Linear Sketches, l0-Sampling & Sparse Recovery

Measurements Instead of the Full Vector

Imagine trying to identify which few shelves changed in a warehouse without recounting every shelf. One option is to record several weighted totals: total change on all shelves, an alternating-sign total, and totals for selected groups. Each update changes those measurements immediately. If only a few shelves have nonzero changes, the combined measurements may reveal them even though the full inventory vector was never stored.

A linear sketch formalizes that idea. A high-dimensional vector $x\in\mathbb R^n$ is mapped to a shorter measurement vector $y=Ax\in\mathbb R^m$, usually with $m\ll n$. A stream update $(i,\Delta)$ means $x_i\leftarrow x_i+\Delta$ and changes the sketch by $y\leftarrow y+\Delta A e_i$, where $e_i$ is the $i$th standard basis vector. Insertions and deletions use the same update rule.

For a tiny example, let

$$ A=\begin{bmatrix}1&1&1&1\\1&-1&1&-1\end{bmatrix},\qquad x=(0,3,0,0)^\mathsf T. $$

Then $Ax=(3,-3)^\mathsf T$. These two measurements happen to identify this one-sparse signal: a positive value in coordinate two produces that pattern. But they cannot identify every vector. Because $A$ has fewer rows than columns, distinct vectors share measurements; recovery requires a restricted signal class such as sparsity and a matrix whose null space does not confuse members of that class.

This viewpoint connects several tasks. Mergeability follows because $A(x+z)=Ax+Az$. An $\ell_0$-sampler tries to return a uniformly random index from the support $\{i:x_i\ne0\}$. Sparse recovery tries to reconstruct all or the most important nonzero coordinates from few measurements. The questions are therefore not “Does compression lose information?”—it must—but “Which information does it preserve, under which model, with what probability, and against which update sequence?”

Linearity, Null Spaces and Sparse Signals

Fix a field or numerical domain and an $m\times n$ matrix $A$. The sketch of $x$ is $S(x)=Ax$. Linearity means $S(\alpha x+\beta z)=\alpha S(x)+\beta S(z)$. In a turnstile stream, update $(i,\Delta)$ adds $\Delta e_i$ to $x$ and therefore adds $\Delta A e_i$ to the sketch. Two shards using the same $A$ can merge by addition; subtracting sketches yields a sketch of the difference.

The null space $\ker(A)=\{h:Ah=0\}$ describes exact indistinguishability. If $Ax=Az$, then $A(x-z)=0$, so $x-z\in\ker(A)$. Conversely, any nonzero $h\in\ker(A)$ makes $x$ and $x+h$ collide. Full recovery for all of $\mathbb R^n$ is impossible when $m\lt n$ because a nontrivial null space must exist.

Sparsity restricts the candidates. Write $\lVert x\rVert_0$ for the number of nonzero coordinates. Exact recovery of every $k$-sparse vector is information-theoretically possible under a fixed matrix precisely when no nonzero null-space vector has at most $2k$ nonzeros. The reason is that the difference of two $k$-sparse vectors is at most $2k$-sparse. If such a difference lies in the null space, the pair collides; if no such vector exists, measurements are injective on the $k$-sparse set. This establishes uniqueness, not an efficient or noise-stable decoder.

Compressed sensing strengthens uniqueness with geometric conditions. The null-space property of order $k$ supports exact $\ell_1$ recovery: for every nonzero $h\in\ker(A)$ and every index set $T$ of size at most $k$, $\lVert h_T\rVert_1\lt\lVert h_{T^c}\rVert_1$. The restricted isometry property approximately preserves the $\ell_2$ norm of sparse vectors and can yield stable recovery under noise and approximate sparsity. Exact constants depend on the theorem and decoder; “RIP” alone is not a complete guarantee.

An $\ell_0$-sampler returns an index $i$ with $x_i\ne0$, ideally uniformly over the final support, and usually reports or estimates $x_i$. It must respect cancellations: an index inserted and later fully deleted is not eligible. Practical constructions use randomized subsampling levels and hashed one-sparse recovery tests. Their guarantee includes a failure probability and assumptions about update adaptivity, arithmetic range, and random seeds.

flowchart TD
    A[Turnstile updates define vector x] --> B[Fixed linear map A]
    B --> C[Sketch y equals Ax]
    C --> D[Update by adding Delta times column i]
    C --> E[Merge compatible shards by addition]
    C --> F[Ask whether two candidates collide]
    F --> G[Difference lies in null space]
    G --> H{Signal restriction}
    H -->|k-sparse| I[No nonzero 2k-sparse null vector]
    H -->|compressible and noisy| J[Null-space or restricted-isometry conditions]
    H -->|support sample| K[Hashed subsampling plus one-sparse tests]
    I --> L[Unique exact sparse solution]
    J --> M[Stable approximate recovery]
    K --> N[l0 sample with stated failure probability]
    classDef navy fill:#17365D,color:#fff,stroke:#17365D;
    classDef teal fill:#147D84,color:#fff,stroke:#0D565B;
    classDef crimson fill:#C6284D,color:#fff,stroke:#861B35;
    classDef purple fill:#6C3BAA,color:#fff,stroke:#472675;
    class A,B,C navy;
    class D,E teal;
    class F,G,H purple;
    class I,J,K teal;
    class L,M,N crimson;

Recovery Conditions and Failure Certificates

Suppose a decoder receives $y=Ax$ and knows that $x$ is $k$-sparse. If two $k$-sparse candidates $x$ and $z$ satisfy the measurements, then $h=x-z$ is at most $2k$-sparse and satisfies $Ah=0$. Thus the absence of nonzero $2k$-sparse null vectors proves uniqueness. Conversely, if such an $h$ exists, split its support into two sets of size at most $k$, write $h=u-v$, and obtain $Au=Av$. That collision is a failure certificate for uniform exact recovery.

Uniqueness can still be numerically fragile. If a unit-norm sparse vector $h$ has $\lVert Ah\rVert_2$ extremely small, measurement noise can make $x$ and $x+h$ nearly indistinguishable. Stable recovery needs a lower bound on measurements of sparse differences, not merely nonzero measurements. Restricted singular values, RIP, robust null-space properties, or expander-based conditions provide different ways to express this separation.

Hashed sparse recovery uses many smaller measurement groups. A coordinate isolated in a bucket can be recognized using checks such as a count, an index-weighted sum, and a verification fingerprint. Peeling decodes isolated coordinates, subtracts their contributions from neighboring buckets, and repeats. The proof must show enough coordinates become isolated, verification rejects mixed buckets with high probability, and accumulated failures remain within the global error budget.

An $\ell_0$-sampler similarly searches for a level at which random subsampling leaves about one surviving support element in some bucket. A one-sparse test identifies it; repetitions reduce failure. If randomness is public and an adaptive adversary sees outcomes or seeds, it may craft updates aligned with collisions. Guarantees proved for an oblivious stream do not automatically survive adaptive interaction.

flowchart TD
    A[Assume two allowed candidates x and z] --> B[Both satisfy Ax equals Az]
    B --> C[Set h equal to x minus z]
    C --> D[Then Ah equals zero]
    D --> E{Is h nonzero and at most 2k-sparse?}
    E -->|Yes| F[Collision certificate: exact uniform recovery impossible]
    E -->|No such h exists| G[Measurements are injective on k-sparse signals]
    G --> H{Need stability under noise?}
    H -->|Yes| I[Require quantitative lower bound on sparse differences]
    H -->|No| J[Uniqueness established]
    I --> K[Choose decoder with matching robust theorem]
    D -. very small Ah rather than zero .-> L[Near-collision: unstable recovery risk]
    classDef navy fill:#17365D,color:#fff,stroke:#17365D;
    classDef teal fill:#147D84,color:#fff,stroke:#0D565B;
    classDef crimson fill:#C6284D,color:#fff,stroke:#861B35;
    classDef purple fill:#6C3BAA,color:#fff,stroke:#472675;
    class A,B,C navy;
    class D,E purple;
    class G,H,I,J,K teal;
    class F,L crimson;

Inventory Changes and Network Anomalies

For inventory reconciliation, let coordinate $i$ be the net change of product $i$ between two snapshots. Sales and receipts create positive or negative turnstile updates. If only a small number of products disagree, sketch subtraction gives $A(x-z)$ and sparse recovery can identify them without transferring full inventories. This model fails when differences are dense or identifiers are inconsistently mapped.

For network monitoring, coordinates can represent flows and values can represent byte-count changes from a baseline. Heavy or sparse anomalies may be recoverable from hashed linear measurements collected across routers. Linearity supports aggregation only when matrices, seeds, epochs, units, and sign conventions match. Packet loss and counter wraparound are measurement-model errors, not decoder noise unless modeled accordingly.

For distributed set or graph differences, coordinates represent possible edges or items and signed updates encode insertions and deletions. $\ell_0$ sampling can return a surviving edge for graph-stream algorithms or a random differing key for diagnostics. The sampler selects from the final nonzero support, not uniformly from update events.

Misleading cases matter. A “sparse anomaly” may be dense after a feature transformation. Two organizations may hash different canonical identifiers to the same coordinate. Floating-point accumulation may violate exact cancellation. An adaptive attacker who learns the sketch can search for a harmful null-space direction. Secret or rotated randomness, overflow-safe arithmetic, validation measurements, and explicit adversary models are part of the guarantee boundary.

Reason About What Can Be Recovered

The disciplined workflow begins with a vector definition and ends with a failure policy. State the update domain, final signal class, randomness model, noise and precision model, and desired output. Then ask what the null space hides, which quantitative property supports the decoder, and how the system detects violated assumptions.