Nonconvex penalties with analytical solutions for one-bit compressive sensing

Abstract

One-bit measurements widely exist in the real world, and they can be used to recover sparse signals. This task is known as the problem of learning halfspaces in learning theory and one-bit compressive sensing (1bit-CS) in signal processing. In this paper, we propose novel algorithms based on both convex and nonconvex sparsity-inducing penalties for robust 1bit-CS. We provide a sufficient condition to verify whether a solution is globally optimal or not. Then we show that the globally optimal solution for positive homogeneous penalties can be obtained in two steps: a proximal operator and a normalization step. For several nonconvex penalties, including minimax concave penalty (MCP), ${\ell }_0$ norm, and sorted ${\ell }_1$ penalty, we provide fast algorithms for finding the analytical solutions by solving the dual problem. Specifically, our algorithm is more than $200$ times faster than the existing algorithm for MCP. Its efficiency is comparable to the algorithm for the ${\ell }_1$ penalty in time, while its performance is much better. Among these penalties, the sorted ${\ell }_1$ penalty is most robust to noise in different settings.

References in corpus (10)

• Nearly unbiased variable selection under minimax concave penalty
• Sparse Regularization via Convex Analysis
• SLOPE - Adaptive variable selection via convex optimization
• Enhanced Low-Rank Matrix Approximation
• The Landscape of Empirical Risk for Non-convex Losses
• Nonconvex Sorted ${\ell }_1$ Minimization for Sparse Approximation
• Bayesian signal reconstruction for 1-bit compressed sensing
• Robust 1-bit Compressive Sensing via Gradient Support Pursuit
• Sparse Recovery via Partial Regularization: Models, Theory and Algorithms
• Nonconvex One-bit Single-label Multi-label Learning

Cited by in corpus (5)

• Computing One-bit Compressive Sensing via Double-Sparsity Constrained Optimization
• Fast Signal Recovery from Saturated Measurements by Linear Loss and Nonconvex Penalties
• Non-convex Lasso-kind approach to compressed sensing for finite-valued signals
• One-Bit Compressed Sensing via One-Shot Hard Thresholding
• From Group Sparse Coding to Rank Minimization: A Novel Denoising Model for Low-level Image Restoration