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.
More recently, @cite_40 has shown that, if @math is a subsampled Gaussian circulant matrix in the binary observation model , PBP can reconstruct the direction of any sparse vector up to an error decaying as @math (see [Thm 4.1] DJR2017 ). Moreover, by adding a random dithering to the linear random measurements before their binarization, the same authors proved that a second-order cone program (SOCP) can fully estimate the vector @math , not only its direction. For the same subsampled circulant sensing matrix, they also proved that their results extend to the dithered, uniformly quantized CS expressed in . In fact, with high probability, and for all effectively sparse signals @math , such that @math is small, the same SOCP program achieves a reconstruction error decaying like @math when @math increases. Their only requirement is that, first, the dithering is made of the addition of a Gaussian random vector with a uniform random vector adjusted to the quantization resolution, and second, that @math is smaller than @math [Thm 6.2] DJR2017 .
@cite_40
2764111657
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.