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*||\leq \epsilon. 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.

1bitcs.pdf
PDF file

In  International Conference on Machine Learning (ICML)

Publisher  Journal of Machine Learning Research

Details

TypeInproceedings
> Publications > One-bit Compressed Sensing: Provable Support and Vector Recovery