One-Bit Compressed Sensing via One-Shot Hard Thresholding

Abstract

This paper concerns the problem of 1-bit compressed sensing, where the goal is to estimate a sparse signal from a few of its binary measurements. We study a non-convex sparsity-constrained program and present a novel and concise analysis that moves away from the widely used notion of Gaussian width. We show that with high probability a simple algorithm is guaranteed to produce an accurate approximation to the normalized signal of interest under the ${\ell }_2$-metric. On top of that, we establish an ensemble of new results that address norm estimation, support recovery, and model misspecification. On the computational side, it is shown that the non-convex program can be solved via one-step hard thresholding which is dramatically efficient in terms of time complexity and memory footprint. On the statistical side, it is shown that our estimator enjoys a near-optimal error rate under standard conditions. The theoretical results are substantiated by numerical experiments.

arXiv commentAccepted to The Conference on Uncertainty in Artificial Intelligence (UAI) 2020

References in corpus (10)

• Nearly unbiased variable selection under minimax concave penalty
• High-dimensional classification using features annealed independence rules
• Sparse principal component analysis and iterative thresholding
• Truncated Power Method for Sparse Eigenvalue Problems
• Nonconvex penalties with analytical solutions for one-bit compressive sensing
• Revisiting Perceptron: Efficient and Label-Optimal Learning of Halfspaces
• Robust 1-bit Compressive Sensing via Gradient Support Pursuit
• Efficient active learning of sparse halfspaces with arbitrary bounded noise
• Lifting high-dimensional nonlinear models with Gaussian regressors
• Attribute-Efficient Learning of Halfspaces with Malicious Noise: Near-Optimal Label Complexity and Noise Tolerance