  In 1-bit compressive sensing (1-bit CS) where 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 = \eta \odot\textrm{sign}
(\Psi x^* + \epsilon)$, where $x^{*}\in \mathcal{R}^{n}, y\in \mathcal{R}^{m}$,
$\Psi \in \mathcal{R}^{m\times n}$, and $\epsilon$ is the random error before
quantization and $\eta\in \mathcal{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 least
squares approach under the over-determined and under-determined settings. For
$m>n$, we show that, up to a constant $c$, with high probability, the least
squares solution $x_{\textrm{ls}}$ approximates $ x^*$ with precision $\delta$
as long as $m \geq\widetilde{\mathcal{O}}(\frac{n}{\delta^2})$. For $m< n$, we
prove that, up to a constant $c$, with high probability, the
$\ell_1$-regularized least-squares solution $x_{\ell_1}$ lies in the ball with
center $x^*$ and radius $\delta$ provided that $m \geq \mathcal{O}( \frac{s\log
n}{\delta^2})$ and $\|x^*\|_0 := 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 to solve 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.
