Search Machine Learning Repository:
**One-Bit Compressed Sensing: Provable Support and Vector Recovery**

**Authors:** *Sivakant Gopi*, *Praneeth Netrapalli*, *Prateek Jain* and *Aditya Nori*

**Conference:** Proceedings of the 30th International Conference on Machine Learning (ICML-13)

**Year:** 2013

**Pages:** 154-162

**Abstract:** In this paper, we study the problem of one-bit compressed sensing ($1$-bit CS), where the goal is to design a measurement matrix $A$ and a recovery algorithm s.t. a $k$-sparse vector $\x^*$ can be efficiently recovered back from signed linear measurements, i.e., $b=\sign(A\x^*)$. This is an important problem in the signal acquisition area and has several learning applications as well, e.g., multi-label classification \cite{HsuKLZ10}. We study this problem in two settings: a) support recovery: recover $\supp(\x^*)$, b) approximate vector recovery: recover a unit vector $\hx$ s.t. $|| \hat{x}-\x^*/||\x^*|| ||_2\leq \epsilon$. For support recovery, we propose two novel and efficient solutions based on two combinatorial structures: union free family 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 almost all the signals. For approximate recovery, we propose the first method to recover sparse vector using a near optimal number of measurements. We also empirically demonstrate effectiveness of our algorithms; we show that our algorithms are able to recover signals with smaller number of measurements than several existing methods.

[pdf] [BibTeX]

authors venues years

Suggest Changes to this paper.

Brought to you by the WUSTL Machine Learning Group. We have open faculty positions (tenured and tenure-track).