> Std. Projects > Sujet 1

Titre: "Déquantification de signaux en acquisition comprimée par méthodes de reconstruction greedy"

Encadrement: Laurent Jacques et Christophe De Vleeschouwer

Résumé: (english description below)

La théorie de l'acquisition comprimée (ou "Compressed Sensing" [1,2]) constitue une réelle révolution dans la manière dont nous pouvons acquérir des signaux informatifs sur le monde qui nous entoure (ex. du son, des images, des vidéos, des données sur graphes). Il n'est désormais plus strictement nécessaire d'échantillonner un signal en fonction de sa limite de bande supposée (comme prescrit par Nyquist-Shannon) mais plutôt en fonction de sa "dimension intrinsèque", c.-à-d., en fonction du nombre de paramètres requis pour représenter ce signal dans une base appropriée de fonctions élémentaires (ex. dans une base DCT, en ondelettes, ou en curvelets). Grâce à cet a priori de "parcimonie" (ou "sparsity") sur la représentation du signal acquis, il est en effet possible de le reconstruire ou de l'estimer au moyen de méthodes non-linéaires en optimisation convexe ou par méthodes itératives dites "greedy".

Face à ce changement de paradigme, il est toutefois nécessaire de digitaliser l'information acquise lors de l'acquisition comprimée et ce au moyen de méthodes de quantifications induisant une distorsion minimale sur les observations. Ceci reste primordial pour transmettre ou enregistrer l'information acquise.

Habituellement, les méthodes de reconstructions en acquisition comprimée assimilent la quantification à un bruit observationnel Gaussien dont l'amplitude est proportionnelle au pas de quantification. Cette manière d'opérer à ses limites et le signal reconstruit n'est par exemple pas nécessairement consistent avec les observations.

Dans ce mémoire, l'étudiant analysera les récentes méthodes de reconstruction de signaux en acquisition comprimée quantifiée (ex. les méthodes Basis Pursuit DeNoise, Basis Pursuit DeQuantizer [3]) afin de développer une méthode itérative "greedy" du type "Iterative Hard Thresholding" (IHT) adaptée à ce modèle d'acquisition. Ce type de processus itératifs offre souvent des temps de calcul très compétitifs par rapport aux autres méthodes exploitant des méthodes d'optimisation convexe assez lourde au niveau calculatoire.

L'étudiant prouvera que sa méthode fonctionne à l'aide de simulations numériques (étude du diagramme de "phase" et de la transition entre bonne et mauvaise reconstruction en fonction du nombre d'observations) et éventuellement de manière théorique en suivant les preuves développées dans d'autres articles [4].

Le travail sera réalisé sur des données simulées à 1-D et sur des images. L'étudiant intéressé par ce sujet devra avoir des connaissances en mathématiques appliquées et/ou en traitement de signaux, et la capacité de programmer en Matlab.

Références:

[1] E. Candès and M. Wakin, "An introduction to compressive sampling". (IEEE Signal Processing Magazine, 25(2), pp. 21 - 30, March 2008) http://dsp.rice.edu/files/cs/CSintro.pdf

[2] L. Jacques and P. Vandergheynst, "Compressed Sensing: When sparsity meets sampling" In "Optical and Digital Image Processing - Fundamentals and Applications", Edited by G. Cristòbal; P. Schelkens; H. Thienpont. Wiley-VCH, April 2011. ISBN:978-3-527-40956-3 http://perso.uclouvain.be/laurent.jacques/uploads/Main/cschap.pdf

[3] L. Jacques, D.K. Hammond, J.M. Fadili, "Dequantizing compressed sensing: When oversampling and non-gaussian constraints combine" Information Theory, IEEE Transactions on 57 (1), 559-571 http://arxiv.org/pdf/0902.2367

[4] T. Blumensath, M. E. Davies, "Iterative Hard Thresholding for Compressed Sensing" Applied and Computational Harmonic Analysis, vol. 27(3):265--274, 2009. http://arxiv.org/abs/0805.0510



Title: "Dequantizing Compressed Sensing with Greedy Methods"

Advisors: Laurent Jacques et Christophe De Vleeschouwer

Abstract:

The Compressed Sensing theory [1,2] (CS) induces a real revolution in the way we sense informative signals about the surrounding world (e.g., audio signals, images, videos, or graph data). A signal has no longer to be sampled at a rate depending on its frequency band limit (as prescribed by the Shannon-Nyquist theorem). The sampling can be operated in function of the signal intrinsic dimension, i.e., depending on the number of parameters required for representing this signal in a convenient basis made of elementary elements (e.g., DCT, wavelets, curvelets, ...). Thanks to this "sparsity" prior on the signal representation, it is indeed possible to reconstruct or estimate this object by non-linear methods in convex optimization or by "greedy" iterative methods.

In front of this paradigm shift, it is nevertheless necessary to digitize the compressed observations by standard quantization methods providing minimum distortion on the sensing. This is of paramount importance for instance for transmitting or storing the sensed data.

Usually, CS reconstruction methods assumes that this quantization induces a simple Gaussian noise distortion whose amplitude is proportional to the quantization bin width. However, this way of doing has some limitation and the reconstructed signal is generally not consistent with the original observation.

In this master project, the student will analyze recent reconstruction methods in the field of quantized compressed sensing (e.g., the Basis Pursuit DeNoise and the Basis Pursuit DeQuantizers methods [3]). He/She will develop a greedy iterative method inspired by the "Iterative Hard Thresholding" (IHT [4]) adapted to this sensing strategy. This kind of iterative method offers generally competitive computational complexity compared to others relying on (heavy) convex optimization techniques.

The student will show that his/her method is effective thanks to numerical simulations (e.g., studying the phase diagram about the good/bad signal reconstruction transition in function of the number of observations). He will possibly show this theoretically by following the proof developped in other articles [4].

The work will be realized on simulated data in 1-D or on images. The interested student must have good skills in applied mathematics and/or signal processing, and good programming skills in Matlab.

References:

[1] E. Candès and M. Wakin, "An introduction to compressive sampling". (IEEE Signal Processing Magazine, 25(2), pp. 21 - 30, March 2008) http://dsp.rice.edu/files/cs/CSintro.pdf

[2] L. Jacques and P. Vandergheynst, "Compressed Sensing: When sparsity meets sampling" In "Optical and Digital Image Processing - Fundamentals and Applications", Edited by G. Cristòbal; P. Schelkens; H. Thienpont. Wiley-VCH, April 2011. ISBN:978-3-527-40956-3 http://perso.uclouvain.be/laurent.jacques/uploads/Main/cschap.pdf

[3] L. Jacques, D. K. Hammond, J.M. Fadili, "Dequantizing compressed sensing: When oversampling and non-gaussian constraints combine" Information Theory, IEEE Transactions on 57 (1), 559-571 http://arxiv.org/pdf/0902.2367

[4] T. Blumensath, M. E. Davies, "Iterative Hard Thresholding for Compressed Sensing" Applied and Computational Harmonic Analysis, vol. 27(3):265--274, 2009. http://arxiv.org/abs/0805.0510