Binary Compressive Sensing via Sum of l1-Norm and l(infinity)-Norm Regularization

We consider the problem of reconstructing a sparse binary signal vector from a limited number of noisy measurements employing compressive sensing technique. Motivated by recent development in compressive sensing and democratic signal representation, this problem is formulated as a least-squares problem regularized by weighted sum of ℓ₁-norm and ℓ_∞-norm. With the benefits of the two norms, this novel formulation is able to promote both sparsity and binary property effectively. Simulations show that our proposed method outperforms many sophisticated techniques especially under small noise. Besides, compared to the state-of-the-art technique based on nonparametric belief propagation, our technique turns out to be more robust under model mismatch.