Conferences: Adaptive Sampling for Fast Sparsity Pattern Recovery
Ramirez Javega, D. Matas and M. Lamarca Orozco

Abstract

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 $\mathbf{x}$ containing only $k << n$
non-zero 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
multi-stage 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.