FoCM 2014 conference

Workshop A2 - Computational Harmonic Analysis, Image and Signal Processing

December 13, 18:00 ~ 18:25 - Room A11

## A one stage Sigma-Delta decoder for compressed sensing measurements

### Rongrong Wang

### University of British Columbia, Canada - rongwang@math.ubc.ca

We analyze how efficiently Sigma-Delta quantization works for quantizing compressed (sub-Gaussian) measurements of sparse and compressible signals. To this end, we propose a one-stage reconstruction algorithm based on convex optimization that yields consistent reconstruction. The algorithm works in the cases of fine and coarse quantization including one-bit quantization, with a reconstruction error decaying inverse polynomially in the quantization order. We show that this decay rate is nearly optimal among all possible reconstruction algorithms by a geometric argument about quantization cells. When we optimize over all quantization orders, the algorithm can achieve root exponential error decay with respect to the "oversampling factor". Finally, we show that by further compressing the quantized data via a Johnson-Lindenstrauss embedding, exponential decay (as a function of the total bit budget) is achieved.

Joint work with This is joint work with Rayan Saab (UCSD) and Ozgur Yilmaz (UBC).