One Scan 1-Bit Compressed Sensing

Based on $α$-stable random projections with small $α$, 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/δ$ measurements (where $δ$ 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.