In this paper we propose a low complexity adaptive algorithm for lossless compressive sampling and reconstruction of sparse signals. Consider a sparse non-negative real signal x containing only 𝑘 << 𝑛 non-zero values. The sampling process obtains 𝑚 measurements by a linear projection y = Ax and, in order to minimize the complexity, we quantize them to binary values. We also define the measurement matrix A to be binary and sparse, enabling the use of a simple message passing algorithm over a graph. We show how to adaptively construct this matrix in a multi-stage process that sequentially reduces the search space until the sparsity pattern is perfectly recovered. As verified by simulation results, the process requires 𝑂(𝑛) operations and 𝑂(𝑘 log(𝑛/𝑘)) samples

Peer Reviewed