Recovering K-sparse N-length vectors in O(K log N) time: Compressed sensing using sparse-graph codes

Abstract

We study the design of measurement matrices for compressed sensing, where the goal is to stably acquire and reconstruct arbitrary K-sparse N-length signals in the presence of noise. We propose a new design framework that simultaneously leads to low measurement cost and low computational cost. In particular, the proposed framework guarantees successful recovery with high probability using O(K log N) measurements with a computational complexity of O(K log N). Both the measurement cost and algorithm runtime are order-optimal for support recovery when K = O (Nδ ) for some 0 <; δ <; 1. To the best of our knowledge, this is the first result that achieves this optimal scaling. The remarkable gains are brought by the proposed measurement structure based on sparse-graph codes, which allows for reconstructions of sparse signals using a simple peeling decoder. More generally, we formally connect general sparse recovery problems with sparse-graph decoding, and demonstrate our design in terms of the measurement cost, computational complexity and performance.