Compressed Sensing with Sparse Binary Matrices: Instance Optimal Error Guarantees in Near-Optimal Time

A compressed sensing method consists of a rectangular measurement matrix, $M\in \text{mathbbm}{R}^{m\times N}$ with $m\ll N$, together with an associated recovery algorithm, $\mathcal{A}:\text{mathbbm}{R}^m\to \text{mathbbm}{R}^N$. Compressed sensing methods aim to construct a high quality approximation to any given input vector $\mathbf{x}\in \text{mathbbm}{R}^N$ using only $M\mathbf{x}\in \text{mathbbm}{R}^m$ as input. In particular, we focus herein on instance optimal nonlinear approximation error bounds for $M$ and $\mathcal{A}$ of the form $\mathrm{\parallel }\mathbf{x}-\mathcal{A}(M\mathbf{x}){\mathrm{\parallel }}_p\le \mathrm{\parallel }\mathbf{x}-{\mathbf{x}}_k^{\mathrm{o}\mathrm{p}\mathrm{t}}{\mathrm{\parallel }}_p+C{k}^{1\mathrm{/}p-1\mathrm{/}q}\mathrm{\parallel }\mathbf{x}-{\mathbf{x}}_k^{\mathrm{o}\mathrm{p}\mathrm{t}}{\mathrm{\parallel }}_q$ for $\mathbf{x}\in \text{mathbbm}{R}^N$, where ${\mathbf{x}}_k^{\mathrm{o}\mathrm{p}\mathrm{t}}$ is the best possible $k$-term approximation to $\mathbf{x}$. In this paper we develop a compressed sensing method whose associated recovery algorithm, $\mathcal{A}$, runs in $O((k\log k)\log N)$-time, matching a lower bound up to a $O(\log k)$ factor. This runtime is obtained by using a new class of sparse binary compressed sensing matrices of near optimal size in combination with sublinear-time recovery techniques motivated by sketching algorithms for high-volume data streams. The new class of matrices is constructed by randomly subsampling rows from well-chosen incoherent matrix constructions which already have a sub-linear number of rows. As a consequence, fewer random bits than previously required are needed in order to select the rows utilized by the fast reconstruction algorithms considered herein.