Efficient Algorithms for Robust One-bit Compressive Sensing

Abstract

While the conventional compressive sensing as-sumes measurements of infinite precision, one-bit compressive sensing considers an extreme setting where each measurement is quantized to just a single bit. In this paper, we study the vector recovery problem from noisy one-bit measure-ments, 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 opti-mization problem that has a closed-form solu-tion. Despite the apparent simplicity, our theoret-ical analysis reveals that the proposed algorithm can recover both the exactly sparse and the ap-proximately sparse vectors. In particular, for a sparse vector with s nonzero elements, the sam-ple complexity is O(s log n/ǫ2), where n is the dimensionality and ǫ is the recovery error. This result improves significantly over the previous-ly best known sample complexity in the noisy setting, which is O(s log n/ǫ4). Second, in the case that the noise model is known, we devel-op 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.