One-bit Compressed Sensing: Provable Support and Vector Recovery

In this paper, we study the problem of onebit compressed sensing (1-bit CS), where the goal is to design a measurement matrix A and a recovery algorithm such that a k-sparse unit vector x∗ can be efficiently recovered from the sign of its linear measurements, i.e., b = sign(Ax∗). This is an important problem for signal acquisition and has several learning applications as well, e.g., multi-label classification (Hsu et al., 2009). We study this problem in two settings: a) support recovery: recover the support of x∗, b) approximate vector recovery: recover a unit vector hat x such that ||hat x – x*||≤ ε. For support recovery, we propose two novel and efficient solutions based on two combinatorial structures: union free families of sets and expanders. In contrast to existing methods for support recovery, our methods are universal i.e. a single measurement matrix A can recover all the signals. For approximate recovery, we propose the first method to recover a sparse vector using a near optimal number of measurements. We also empirically validate our algorithms and demonstrate that our algorithms recover the true signal using fewer measurements than the existing methods.