One Scan 1-Bit Compressed Sensing
  Based on $\alpha$-stable random projections with small $\alpha$, we develop a
simple algorithm for compressed sensing (sparse signal recovery) by utilizing
only the signs (i.e., 1-bit) of the measurements. Using only 1-bit information
of the measurements results in substantial cost reduction in collection,
storage, communication, and decoding for compressed sensing. The proposed
algorithm is efficient in that the decoding procedure requires only one scan of
the coordinates. Our analysis can precisely show that, for a $K$-sparse signal
of length $N$, $12.3K\log N/\delta$ measurements (where $\delta$ is the
confidence) would be sufficient for recovering the support and the signs of the
signal. While the method is very robust against typical measurement noises, we
also provide the analysis of the scheme under random flipping of the signs of
the measurements.
  \noindent Compared to the well-known work on 1-bit marginal regression (which
can also be viewed as a one-scan method), the proposed algorithm requires
orders of magnitude fewer measurements. Compared to 1-bit Iterative Hard
Thresholding (IHT) (which is not a one-scan algorithm), our method is still
significantly more accurate. Furthermore, the proposed method is reasonably
robust against random sign flipping while IHT is known to be very sensitive to
this type of noise.
