Conferences: Adaptive Sampling for Fast Sparsity Pattern Recovery Ramirez Javega, D. Matas and M. Lamarca OrozcoAbstractIn this paper we propose a low complexity adaptive algorithm for lossless compressive sampling and reconstruction of sparse signals. Consider a sparse nonnegative real signal $\mathbf{x}$ containing only $k << n$ nonzero values. The sampling computes m measurements by a linear projection $\mathbf{y}=\mathbf{Ax}$. To minimize the complexity, we quantize the measurements to binary values and define the measurement matrix A to be sparse, enabling the use of a simple message passing algorithm over a graph. We show how to construct this matrix in a multistage process that sequentially reduces the search space until the sparsity pattern is perfectly recovered. As verified by simulation results, the process requires $O(n)$ comparison operations and $O(k log(n/k))$ samples. 
