A compressed sensing method consists of a rectangular measurement matrix, $M \in \mathbbm{ R}^{ m \times N}$ with $m \ll N$, together with an associated recovery algorithm, $\mathcal{ A}: \mathbbm{ R}^m \rightarrow \mathbbm{ R}^N$. Compressed sensing methods aim to construct a high quality approximation to any given input vector ${ \bf x} \in \mathbbm{ R}^N$ using only $M { \bf x} \in \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 $ \| { \bf x} - \mathcal{ A} (M { \bf x}) \|_p \leq \| { \bf x} - { \bf x}^{ \rm opt}_k \|_p + C k^{ 1/p - 1/q} \| { \bf x} - { \bf x}^{ \rm opt}_k \|_q$ for ${ \bf x} \in \mathbbm{ R}^N$, where ${ \bf x}^{ \rm opt}_k$ is the best possible $k$-term approximation to ${ \bf 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.
Categories: cs.IT math.IT math.NA