Title: A Fast Noniterative Algorithm for Compressive Sensing Using Binary Measurement Matrices,
Abstract: In this paper we present a new algorithm for compressive sensing that makes
use of binary measurement matrices and achieves exact recovery of ultra sparse
vectors, in a single pass and without any iterations. Due to its noniterative
nature, our algorithm is hundreds of times faster than $\ell_1$-norm
minimization, and methods based on expander graphs, both of which require
multiple iterations. Our algorithm can accommodate nearly sparse vectors, in
which case it recovers index set of the largest components, and can also
accommodate burst noise measurements. Compared to compressive sensing methods
that are guaranteed to achieve exact recovery of all sparse vectors, our method
requires fewer measurements However, methods that achieve statistical recovery,
that is, recovery of almost all but not all sparse vectors, can require fewer
measurements than our method.