@inproceedings{gopi2013one-bit,
author = {Gopi, Sivakant and Netrapalli, Praneeth and Jain, Prateek and Nori, Aditya},
title = {One-bit Compressed Sensing: Provable Support and Vector Recovery},
booktitle = {International Conference on Machine Learning (ICML)},
year = {2013},
month = {June},
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.},
publisher = {Journal of Machine Learning Research},
url = {http://approjects.co.za/?big=en-us/research/publication/one-bit-compressed-sensing-provable-support-and-vector-recovery/},
edition = {International Conference on Machine Learning (ICML)},
}