Quantized compressed sensing for random circulant matrices

We provide the first analysis of a non-trivial quantization scheme for compressed sensing with structured measurements. We consider compressed sensing matrices consisting of rows selected randomly, without replacement, from a circulant matrix generated by a random subgaussian vector. We quantize the measurements using stable, possibly one-bit, Sigma-Delta schemes, and reconstruct the signal via convex optimization. We show that the part of the reconstruction error due to quantization decays polynomially in the number of measurements. This is in-line with analogous results on Sigma-Delta quantization associated with random subgaussian matrices, and significantly better than results associated with the widely assumed memoryless scalar quantization. Moreover, we prove our approach is stable and robust; the reconstruction error degrades gracefully in the presence of noise and when the underlying signal is not strictly sparse. The analysis relies on results concerning subgaussian chaos processes and a variation of McDiarmid's inequality. (C) 2019 Published by Elsevier Inc.