Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
One-bit Compressed Sensing: Provable Support and Vector Recovery

Sivakant Gopi, Praneeth Netrapalli, Prateek Jain, and Aditya V. Nori

Abstract

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.

Details

Publication typeInproceedings
Published inInternational Conference on Machine Learning (ICML)
PublisherJournal of Machine Learning Research
> Publications > One-bit Compressed Sensing: Provable Support and Vector Recovery