February Fourier Talks 2016

We study the under-addressed "quantization" stage that is implicit in any compressed sensing signal acquisition paradigm. Here quantization refers the conversion of the real (or complex) valued compressive samples to bit-streams that can be transmitted, stored, and processed using digital media. We propose using Sigma-Delta quantization for the initial "analog-to-digital conversion" followed by a compression stage comprised of a discrete Johnson-Lindenstrauss embedding. The corresponding reconstruction scheme is based on convex optimization. We show that this encoding/decoding method yields near-optimal rate-distortion guarantees for sparse and compressible signals and is robust to noise. Our results hold for sub-Gaussian (including Gaussian and Bernoulli) random compressed sensing measurements, and they hold for high bit-depth quantizers as well as for coarse quantizers including 1-bit quantization. This is joint work with Rayan Saab and Rongrong Wang.