Trust, but verify: Fast and accurate signal recovery from 1-bit compressive measurements

The recently emerged \emph{compressive sensing} (CS) framework aims to acquire signals at reduced sample rates compared to the classical Shannon-Nyquist rate. To date, the CS theory has assumed primarily real-valued measurements; it has recently been demonstrated that accurate and stable signal acquisition is still possible even when each measurement is quantized to just a single bit. This property enables the design of simplified CS acquisition hardware based around a simple sign comparator rather than a more complex analog-to-digital converter; moreover, it ensures robustness to gross non-linearities applied to the measurements. In this paper we introduce a new algorithm --- restricted-step shrinkage (RSS) --- to recover sparse signals from 1-bit CS measurements. In contrast to previous algorithms for 1-bit CS, RSS has provable convergence guarantees,
is about an order of magnitude faster, and achieves higher average recovery signal-to-noise ratio. RSS is similar in spirit to \emph{trust-region} methods for non-convex optimization on the unit sphere, which are relatively unexplored in signal processing and hence of independent interest.