Sparse Signal Recovery from Random Measurements

Given the compressed sensing measurements of an unknown vector $z\in {\mathbb{R}}^n$ using random matrices, we present a simple method to determine $z$ without solving any optimization problem or linear system. Our method uses $\mathrm{\Theta }(\log n)$ random sensing matrices in ${\mathbb{R}}^{k\times n}$ and runs in $O(kn\log n)$ time, where $k=\mathrm{\Theta }(s\log n)$ and $s$ is the number of nonzero coordinates in $z$. We adapt our method to determine the support set of $z$ and experimentally compare with some optimization-based methods on binary signals.