Robust decoding from 1-bit compressive sampling with ordinary and regularized least squares

Jian Huang, Yuling Jiao, Xiliang Lu, Liping Zhu

Research output: Journal article publicationJournal articleAcademic researchpeer-review

6 Citations (Scopus)


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 n , y ∈ R m , Ψ ∈ R m × n , and is the random error before quantization and η ∈ R n 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 ls approximates x with precision δ as long as m ≥ O e ( δ n 2 ). For m < n, we prove that, up to a constant c, with high probability, the ` 1 -regularized least-squares solution x ` 1 lies in the ball with center x and radius δ provided that m ≥ O( s log δ 2 n ) and kx k0:= 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.

Original languageEnglish
Pages (from-to)A2062-A2086
JournalSIAM Journal on Scientific Computing
Issue number4
Publication statusPublished - 1 Jan 2018


  • 1-bit compressive sensing
  • -regularized least squares
  • Continuation
  • One-step convergence
  • Primal dual active set algorithm

ASJC Scopus subject areas

  • Computational Mathematics
  • Applied Mathematics

Cite this