A fast single-pass algorithm for compressive sensing based on binary measurement matrices

摘要

In this paper we present a new algorithm for compressive sensing that makes use of binary measurement matrices and achieves exact recovery of sparse vectors, in a single pass, without any iterations. Our algorithm is hundreds of times faster than methods based on expander graphs (which require multiple iterations). Moreover, our method requires the fewest measurements amongst all methods that use binary measurement matrices. The algorithm can accommodate “nearly” sparse vectors, in which case it recovers the largest components, and can also accommodate noisy measurements. Our algorithm has parallels with ℓ₁-norm minimization, but runs about a hundred times faster.