Quantized Compressed Sensing for Partial Random Circulant Matrices

We provide the first analysis of a non-trivial quantization scheme for compressed sensing measurements arising from structured measurements. Specifically, our analysis studies compressed sensing matrices consisting of rows selected at random, 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 use a reconstruction method based on 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 Gaussian or subgaussian matrices, and significantly better than results associated with the widely assumed memoryless scalar quantization.