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 language||English (US)|
|Number of pages||9|
|Journal||Journal of Machine Learning Research|
|State||Published - Jan 1 2015|
|Event||18th International Conference on Artificial Intelligence and Statistics, AISTATS 2015 - San Diego, United States|
Duration: May 9 2015 → May 12 2015