Robust Decoding from 1-Bit Compressive Sampling with Ordinary and Regularized Least Squares

In 1-bit compressive sensing (1-bit CS) where a target signal is coded into a binary measurement, one goal is to recover the signal from noisy and quantized samples. Mathematically, the 1-bit CS model reads y = η sign (Ψ x^* + ε), where x*∈ Rⁿ, y∈ Rᵐ, Ψ ∈ Rm× n, and ε is the random error before quantization and η∈ Rⁿ is a random vector modeling the sign flips. Due to the presence of nonlinearity, noise, and sign flips, it is quite challenging to decode from the 1-bit CS. In this paper, we consider a least squares approach under the overdetermined and underdetermined settings. For $m>n$, we show that, up to a constant c, with high probability, the least squares solution xₗₛ approximates x^* with precision δ as long as m ≥O(n/δ²). For $m< n$, we prove that, up to a constant c, with high probability, the ₁-regularized least-squares solution x₁ lies in the ball with center x^* and radius δ provided that m ≥ O( slog n/δ²) and \|x^*\|₀ := s < m. We introduce a Newton type method, the so-called primal and dual active set (PDAS) algorithm, to solve the nonsmooth optimization problem. The PDAS possesses the property of one-step convergence. It only requires solving a small least squares problem on the active set. Therefore, the PDAS is extremely efficient for recovering sparse signals through continuation. We propose a novel regularization parameter selection rule which does not introduce any extra computational overhead. Extensive numerical experiments are presented to illustrate the robustness of our proposed model and the efficiency of our algorithm.