Abstract

While the conventional compressive sensing assumes measurements of infinite precision, onebit compressive sensing considers an extreme setting where each measurement is quantized to just a single bit. In this paper, we study the vect recovery problem from noisy one-bit measurements, and develop two novel algorithms with formal theoretical guarantees. First, we propose a passive algorithm, which is very efficient in the sense it only needs to solve a convex optimization problem that has a closed-form solution. Despite the apparent simplicity, our theoretical analysis reveals that the proposed algorithm can recover both the exactly sparse and the approximately sparse vectors. In particular, for a sparse vector with s nonzero elements, the sample complexity is where n is the dimensionality and is the recovery error. This result improves significantly over the previously best known sample complexity in the noisy setting, which is Second, in the case that the noise model is known, we develop an adaptive algorithm based on the principle of active learning. The key idea is to solicit the sign information only when it cannot be inferred from the current estimator. Compared with the passive algorithm, the adaptive one has a lower sample complexity if a high-precision solution is desired. Proceedings of the 31 st International Conference on MachLearning, Beijing, China, 2014. JMLR: W&CP volume 32. Copright 2014 by the author(s).