Abstract

In this paper, we propose a novel algorithm based on nonconvex sparsity-inducing penalty for onebit compressed sensing. We prove that our algorithm has a sample complexity of for strong signals, and for weak signals, where s is the number of nonzero entries in the signal vector, d is the signal dimension and  is the recovery error. For general signals, the sample complexity of our algorithm lies between and . This is a remarkable improvement over the existing best sample complexity . Furthermore, we show that our algorithm achieves exact support recovery with high probability for strong signals. Our theory is verified by extensive numerical experiments, which clearly illustrate the superiority of our algorithm for both approximate signal and support recovery in the noisy setting.