Seminar Details
2010-05-11 (14.00) : Dequantizing Compressed Sensing: Recovering Quantization Consistency with Oversampling and Non-Gaussian Constraints
At Euler building
Organized by Mathematical Engineering
Speaker :
Jacques, Laurent
Abstract :
Compressed Sensing is a recent revolution in (general) signal sampling whose advent is due to the seminal works
of E. Candès, T. Tao, J. Romberg and D. Donoho in 2006. In short, this theory shows that, without loss of information, a
signal can be sampled in function of its intrinsic dimension rather than according to its cutoff frequency. The reason of
this seemingly magic statement comes from (i) a generalization of the sampling into any linear (and often random) measurement process,
(ii) a prior knowledge of the signal structure, i.e. its assumed sparsity or compressibility in a certain basis (e.g. wavelets, DCT, curvelets, ...),
and (iii) the use of non-linear reconstruction techniques (e.g. Basis Pursuit, Lasso, Greedy methods, ...).
Quantization of measurements is however a common procedure that Compressed Sensing theory has to consider carefully. First, on a practical point
of view, any coder or device integrating a CS encoding, i.e. the random projections of the signal, has to transmit data to the decoder in a digital
way so as for instance to limit transmission errors. Second, from an Information Theory standpoint, it is better to consider the real compression
achieved by CS by counting the number of bits necessary to represent the signal with a controlled error, i.e. a binary representation achieved by
quantization.
In this talk, after a brief introduction of the CS theory, I will present a new reconstruction method, called Basis Pursuit DeQuantizer (BPDQ),
to be used when the random measurements of a signal have undergone a scalar quantization. This reconstruction relies on a convex optimization that
minimizes the sparsity of the signal to reconstruct under a fidelity constraint that is not expressed in the l2-norm anymore, as for the common Basis
Pursuit DeNoising (BPDN) reconstruction, but in the lp-norm (with p >= 2). Taking p higher than 2 provides indeed a better Quantization Consistency of
the reconstructed signal, i.e. the fact that quantizing the remeasured reconstruction is close to the original measurements. For the non-uniform case,
we show furthermore that a simple "weighting" of the lp-norm, with weight related to the quantization bin widths, is sufficient to provide provable
guarantees on the quality of the reconstructed signal.
An important message of this work is that the quality of the reconstruction improves with p in oversampled situation, i.e. when the number of measurements
is higher than a minimal value increasing with p. The reason of this stability relies on a generalization of the Restricted Isometry Property (RIP),
conditioning somehow the CS measurement matrix, to any embedding between two normed spaces. This property is again respected with a controlled
probability by Random Gaussian matrices when these two spaces are the (weighted) lp Banach space and the l2 Hilbert space, i.e. the case used to prove
BPDQ stability. We conclude this talk by providing some simulations of signal and image reconstructions from quantized random measurements.