One-bit compressed sensing with the κ-support norm

Sheng Chen, Arindam Banerjee

Research output: Contribution to journalConference articlepeer-review

6 Scopus citations


In one-bit compressed sensing (1-bit CS), one attempts to estimate a structured parameter (signal) only using the sign of suitable linear measurements. In this paper, we investigate 1-bit CS problems for sparse signals using the recently proposed k-support norm. We show that the new estimator has a closed-form solution, so no optimization is needed. We establish consistency and recovery guarantees of the estimator for both Gaussian and sub-Gaussian random measurements. For Gaussian measurements, our estimator is comparable to the best known in the literature, along with guarantees on support recovery. For sub-Gaussian measurements, our estimator has an irreducible error which, unlike existing results, can be controlled by scaling the measurement vectors. In both cases, our analysis covers the setting of model misspec-ification, i.e., when the true sparsity is unknown. Experimental results illustrate several strengths of the new estimator.

Original languageEnglish (US)
Pages (from-to)138-146
Number of pages9
JournalJournal of Machine Learning Research
StatePublished - Jan 1 2015
Event18th International Conference on Artificial Intelligence and Statistics, AISTATS 2015 - San Diego, United States
Duration: May 9 2015May 12 2015


Dive into the research topics of 'One-bit compressed sensing with the κ-support norm'. Together they form a unique fingerprint.

Cite this