Imaging and Computing Seminar

Jalal Fadili, ENSI Caen, France

Dequantizing Compressed Sensing: from recovery guarantees to nonsmooth optimization

This talk would be divided in two parts. The first one will focus on several optimization problems involved in linear inverse problems where the solution is assumed to be sparsely represented in an overcomplete dictionary of waveforms. These problems are formalized within a unified framework of convex optimization theory, and invoke tools from convex analysis (e.g. duality, proximity operators) and maximal monotone operator splitting. Fast iterative splitting algorithms are proposed to solve them. This framework includes some previously proposed algorithms as a special case. In the second part, we study the problem of recovering sparse or compressible signals from uniformly quantized measurements. Toward this goal, a new class of convex optimization decoders is introduced, coined Basis Pursuit DeQuantizer of moment $p$ (BPDQ$_p$), that model the quantization distortion more faithfully than the commonly used BPDN or Lasso. We show that in oversampled situations, the performance of the BPDQ$_p$ decoders are significantly better than that of BPDN, with reconstruction error due to quantization divided by $\sqrt{p+1}$. This reduction relies on a modified Restricted Isometry Property of the sensing matrix expressed in the $\ell_p$-norm (RIP$_p$); a property satisfied by Gaussian random matrices with high probability. The challenging BPDQ$_p$ optimization program are solved by monotone operator splitting methods presented in the first part.