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.
), Kolmogorov entropy (KE, Sec. ), union of low-dimensional subspaces (ULS), low-rank models (LR), second order cone programming (SOCP), Gaussian random matrices (GRM), sub-Gaussian random matrices (SGRM), and subsampled Gaussian circulant matrix (SGCM) @cite_40 . The concept of multiple of @math '' is defined in Sec. . We now provide a comparison of our work with the most relevant literature. This one is connected to 1-bit CS, QCS or other non-linear sensing models, when these are applied componentwise (as for scalar quantization) on compressive sensing measurements, possibly with a random or adaptive pre-quantization dithering for certain studies, with algorithms similar or related to PBP. Most of the works presented below are summarized in Table , reporting there, amongst other aspects, the sensing model, the algorithm, the type of admissible sensing matrices and the low-complexity sets chosen in each of the referenced works.
@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.