Thanks to Nuit Blanche for pointing me towards the paper “Exact Sparse Recovery with L0 Projections” by Ping Li and Cun-Hui Zhang (2013). The paper describes an algorithm (Min+Gap(3)), which perfectly recovers $x\in R^N$ from $M_0$ random measurements $y_i\in R$. The vector $y$ is generated by
$y = S x$
where $S\in R^{N\times M},\ ||x||_0 = K,\ K\ll N,\ s_{ij} \sim S(\alpha, 1)$, and $S(\alpha, 1)$ denotes an $\alpha$-stable distribution with unit scale. Typically the number of measurements required for exact recovery is “about $5 K$”. More specifically,
“$M_0 = K \log ((N − K)/\delta)$ measurements are sufficient for detecting all zeros with at least probability $1 − \delta$.”
Li and Zhang illustrate the effectiveness of their algorithm by applying it to a simple video stream exactly recovering the video from measurements constructed from the differences between frames. They also discuss an application to finding “heavy hitters” (“elephant detection”) in marketing data (see e.g “Compressive sensing medium access control for wireless lans” Globecom, 2012 and “A data streaming algorithm for estimating entropies of od flows” IMC, San Diego, CA, 2007.).
The idea for the algorithm seems to have stemmed from Piotr Indyk’s paper “Stable distributions, pseudorandom generators, embeddings, and data stream computation.” Li and Zang state that Indyk estimated “the $\alpha$-th frequency moment $\sum_{i=1}^N |x_i|^\alpha$” using random measurements generated from an $\alpha$-stable distribution instead of the harder problem of recovering $x$ exactly.
In numerical simulations, they compare their algorithm to orthogonal matching pursuit and linear programming. Additionally, detailed proofs of the their algorithm’s effectiveness are provided.