  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 $\ell_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.
