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).