1-bit compressive sensing: reformulation and RRSP-based sign recovery theory

Yun-Bin Zhao, Chunlei Xu (Contributor)

Research output: Contribution to journalArticlepeer-review

7 Citations (Scopus)


Recently, the 1-bit compressive sensing (1-bit CS) has been studied in the field of sparse signal recovery. Since the amplitude information of sparse signals in 1-bit CS is not available, it is often the support or the sign of a signal that can be exactly recovered with a decoding method. In this paper, we first show that a necessary assumption (that has been overlooked in the literature) should be made for some existing theories and discussions for 1-bit CS. Without such an assumption, the found solution by some existing decoding algorithms might be inconsistent with 1-bit measurements. This motivates us to pursue a new direction to develop uniform and nonuniform recovery theories for 1-bit CS with a new decoding method which always generates a solution consistent with 1-bit measurements. We focus on an extreme case of 1-bit CS, in which the measurements capture only the sign of the product of a sensing matrix and a signal. We show that the 1-bit CS model can be reformulated equivalently as an ℓ0-minimization problem with linear constraints. This reformulation naturally leads to a new linear-program-based decoding method, referred to as the 1-bit basis pursuit, which is remarkably different from existing formulations. It turns out that the uniqueness condition for the solution of the 1-bit basis pursuit yields the so-called restricted range space property (RRSP) of the transposed sensing matrix. This concept provides a basis to develop sign recovery conditions for sparse signals through 1-bit measurements. We prove that if the sign of a sparse signal can be exactly recovered from 1-bit measurements with 1-bit basis pursuit, then the sensing matrix must admit a certain RRSP, and that if the sensing matrix admits a slightly enhanced RRSP, then the sign of a k-sparse signal can be exactly recovered with 1-bit basis pursuit.
Original languageEnglish
Pages (from-to)2049-2074
Number of pages25
JournalScience China Mathematics
Issue number10
Early online date18 Jul 2016
Publication statusPublished - Oct 2016


  • 1-bit compressive sensing
  • , restricted range space property
  • 1-bit basis pursuit
  • linear program
  • `0-minimization
  • sparse signal recovery


Dive into the research topics of '1-bit compressive sensing: reformulation and RRSP-based sign recovery theory'. Together they form a unique fingerprint.

Cite this