One-bit Compressed Sensing: Provable Support and Vector Recovery

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

June 2013

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.

Publication type | Inproceedings |

Published in | International Conference on Machine Learning (ICML) |

Publisher | Journal of Machine Learning Research |

- Hashing Hyperplane Queries to Near Points with Applications to Large-Scale Active Learning
- Holmes: Effective Statistical Debugging via Efficient Path Profiling
- Verification as Learning Geometric Concepts

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