Measurement Matrix Design for Sample-Efficient Binary Compressed Sensing

This letter investigates the problem of recovering a binary-valued signal from compressed measurements of its convolution with a known finite impulse response filter. We show that it is possible to attain optimum sample complexity for exact recovery (in absence of noise) with a computationally efficient algorithm. We achieve this by adopting an algorithm-measurement co-design strategy where the measurement matrix is designed as a function of the filter, such that the recovery of binary signals with arbitrary sparsity is possible by using a sequential decoding algorithm. Such a filter-dependent sampler design can overcome the computational challenges associated with enforcing binary constraints, and enable us to operate in “extreme compression” regimes, where the number of measurements can be much smaller than the sparsity level.