In Compressive Sensing theory and its applications, quantization of signal measurements, as integrated into any realistic sensing model, impacts the quality of signal reconstruction. In fact, there even exist incompatible combinations of quantization functions (e.g., the 1-bit sign function) and sensing matrices (e.g., Bernoulli) that cannot lead to an arbitrarily low reconstruction error when the number of observations increases. This work shows that, for a scalar and uniform quantization, provided that a uniform random vector, or "random dithering", is added to the compressive measurements of a low-complexity signal (e.g., a sparse or compressible signal, or a low-rank matrix) before quantization, a large class of random matrix constructions known to respect the restricted isometry property (RIP) are made "compatible" with this quantizer. This compatibility is demonstrated by the existence of (at least) one signal reconstruction method, the "projected back projection" (PBP), whose reconstruction error is proved to decay when the number of quantized measurements increases. Despite the simplicity of PBP, which amounts to projecting the back projection of the compressive observations (obtained from their multiplication by the adjoint sensing matrix) onto the low-complexity set containing the observed signal, we also prove that given a RIP matrix and for a single realization of the dithering, this reconstruction error decay is also achievable uniformly for the sensing of all signals in the considered low-complexity set. We finally confirm empirically these observations in several sensing contexts involving sparse signals, low-rank matrices, and compressible signals, with various RIP matrix constructions such as sub-Gaussian random matrices and random partial Discrete Cosine Transform (DCT) matrices.
Consider the recovery of an unknown signal @math from quantized linear measurements. In the one-bit compressive sensing setting, one typically assumes that @math is sparse, and that the measurements are of the form @math . Since such measurements give no information on the norm of @math , recovery methods typically assume that @math . We show that if one allows more generally for quantized affine measurements of the form @math , and if the vectors @math are random, an appropriate choice of the affine shifts @math allows norm recovery to be easily incorporated into existing methods for one-bit compressive sensing. In addition, we show that for arbitrary fixed @math in the annulus @math , one may estimate the norm @math up to additive error @math from @math such binary measurements through a single evaluation of the inverse Gaussian error function. Finally, all of our recovery guarantees can be made universal over sparse vectors in the sense that with high probability, one set of measurements and thresholds can successfully estimate all sparse vectors @math in a Euclidean ball of known radius. Binary measurements arise naturally in a variety of statistics and engineering applications. They may be inherent to the problem—for example, in determining the relationship between genetics and the presence or absence of a disease—or they may be a result of extreme quantization. A recent influx of literature has suggested that using prior signal information can greatly improve the ability to reconstruct a signal from binary measurements. This is exemplified by one-bit compressed sensing , which takes the compressed sensing model but assumes that only the sign of each measurement is retained. It has recently been shown that the number of one-bit measurements required for signal estimation mirrors that of unquantized compressed sensing. Indeed, @math -sparse signals in @math can be estimated (up to normalization) from @math one-bit measurements. Nevertheless, controlling the precise accuracy of the error estimate remains an open challenge. In this paper, we focus on optimizing the decay of the error as a function of the oversampling factor @math , where @math is the number of measurements. It is known that the error in reconstructing sparse signals from standard one-bit measurements is bounded below by @math . Without adjusting the measurement procedure, reducing this polynomial error decay rate is impossible. However, we show that an adaptive choice of the thresholds used for quantization can lower the error rate to @math . This improves upon guarantees for other methods of adaptive thresholding, such as sigma–delta quantization. We develop a general recursive strategy to achieve this exponential decay and two specific polynomial-time algorithms, which fall into this framework, one based on convex programming and one on hard thresholding. Our work bridges the one-bit compressed sensing model, in which the engineer controls the measurement procedure, to sigma–delta and successive approximation quantization. Moreover, the principle is extendable to signal reconstruction problems in a variety of binary statistical models as well as statistical estimation problems like logistic regression. In this paper we consider memoryless one-bit compressed sensing with randomly subsampled Gaussian circulant matrices. We show that in a small sparsity regime and for small enough accuracy @math , @math measurements suffice to reconstruct the direction of any @math -sparse vector up to accuracy @math via an efficient program. We derive this result by proving that partial Gaussian circulant matrices satisfy an @math RIP-property. Under a slightly worse dependence on @math , we establish stability with respect to approximate sparsity, as well as full vector recovery results. Quantization of compressed sensing measurements is typically justified by the robust recovery results of Candes, Romberg and Tao, and of Donoho. These results guarantee that if a uniform quantizer of step size ź is used to quantize m measurements y=źx of a k-sparse signal xźźN, where ź satisfies the restricted isometry property, then the approximate recovery x# via l1-minimization is within O(ź) of x. The simplest and commonly assumed approach is to quantize each measurement independently. In this paper, we show that if instead an rth-order ΣΔ (Sigma---Delta) quantization scheme with the same output alphabet is used to quantize y, then there is an alternative recovery method via Sobolev dual frames which guarantees a reduced approximation error that is of the order ź(k m)(rź1 2)ź for any 0<ź<1, if mźr,źk(logN)1 (1źź). The result holds with high probability on the initial draw of the measurement matrix ź from the Gaussian distribution, and uniformly for all k-sparse signals x whose magnitudes are suitably bounded away from zero on their support. 