Offre de Stage Master 2 / Inge 3 Fast Orthonormal Matching Pursuit, 2007-2008

Titre : Vers des algorithmes de décomposition parcimonieuse à grande échelle précis et rapides

Mots-clés: algorithme rapide de recherche approchée, décomposition parcimonieuse, moindres carrés,
optimisation numérique, problèmes inverses, Compressed Sensing, réseaux de capteurs.

Sujet :

L'objectif du stage est de démontrer la faisabilité de l'analyse parcimonieuse précise et rapide de signaux ou d'images de très grande dimension. L'approche envisagée combinera des avancées récentes en informatique théorique (algorithmes de recherche approchée de complexité sous-linéaire) et des techniques avancées de calcul numérique (résolution de grands systèmes  linéaires avec des matrices creuses).

La décomposition d'un signal, d'une image, d'une vidéo, sous forme de combinaison linéaire parcimonieuse de formes d'onde (ou imagettes) élémentaires appelées atomes choisis dans un "dictionnaire" redondant est un élément clé pour beaucoup d'applications en traitement du signal telles que la compression, le débruitage, la séparation de sources ou la technologie émergente du Compressed Sensing, qui devrait permettre l'acquisition sous forme directement compressée de données de très grande dimension (haute-résolution, réseaux de capteurs, multiples modalités, etc.).

Le problème de décomposition parcimonieuse, qui consiste à déterminer le meilleur sous-ensemble de k atomes parmi N pour représenter le signal considéré, est a priori combinatoire. Cependant, des avancées théoriques récentes ont montré que, si la solution est suffisamment parcimonieuse, alors elle peut également être obtenue par programmation convexe ou par un algorithme itératif de poursuite orthogonale [Tropp]. Bien qu'infiniment plus rapides qu'une recherche combinatoire, ces approches restent néanmoins très gourmandes en ressources de calcul.

L'équipe METISS de l'IRISA a développé un implémentation très rapide [MPTK] d'un algorithme de poursuite non orthogonal (matching pursuit), qui permet de traiter certains problèmes de très grande échelle. MPTK a rendu accessible l'exploitation des décompositions parcimonieuses sur de bases de données de grande
dimension, mais la précision d'analyse de la poursuite non orthogonale pour le Compressed Sensing ou la séparation de sources sonores est sensiblement inférieure à celle de la poursuite orthogonale.

 
L'objectif du stage est de franchir un nouveau cap dans le compromis rapidité / précision, en combinant la rapidité de MPTK (poursuite non-orthogonale) et la précision d'analyse de la poursuite orthogonale.  Le principal défi consistera à proposer des structures de données et des algorithmes d'orthogonalisation,
exacte ou approchée, dont la complexité soit contrôlée pour la gamme de problèmes de grande échelle considérée. On s'appuiera pour cela sur une analyse de la littérature récente en analyse parcimonieuse [Gilbert,Blumensath]  et des techniques de résolution de grands problèmes linéaires avec des matrices creuses [Golub,Bjorck].  On cherchera également à réduire le coût de l'étape initiale des algorithmes de poursuite, la plus coûteuse à ce jour, qui consiste à calculer les corrélations entre le signal analysé et les atomes du dictionnaire. On pourra s'inspirer des résultats récents montrant comment on peut déterminer les plus grands coefficients d'une transformée de Fourier pour une fraction du coût qu'aurait requis le calcul de celle-ci [Gilbert2].
  
La prise en main des algorithmes existants et le prototypage des méthodes proposées se feront en matlab. Les algorithmes retenus seront implémentés en C++ pour être incorporés dans MPTK. On validera expérimentalement la rapidité et la précision des algorithmes obtenus pour des problèmes de représentation et de séparation de sources sonores. Ce stage est susceptible de déboucher sur une thèse.

Bibliographie :

• [Tropp] Tropp, J., Greed is good : Algorithmic results for sparse approximation, IEEE Trans. Inform. Theory, Vol. 50, No. 10, pp. 2231--2242, oct. 2004.
• [MPTK] Krstulovic, S. and Gribonval, R., MPTK : Matching Pursuit made tractable, Proc. Int. Conf. Acoust. Speech Signal Process. (ICASSP'06), Vol. 3, pp. III-496 -- III-499, Toulouse, 2006.
• [Gilbert] Anna Gilbert, Martin Strauss, Joel Tropp, and Roman Vershynin, One sketch for all: Fast algorithms for compressed sensing. (To appear in Proc. STOC 2007)
• [Blumensath] Thomas Blumensath and Mike E. Davies, Gradient pursuits. (Preprint, 2007, http://www.see.ed.ac.uk/~tblumens/papers/BDGP07.pdf)
• [Golub] Golub, G. H and Van Loan, C.F., Matrix Computations, 2nd edition, The John Hopkins University Press, 1989.
• [Bjorck] Bjorck, A., Numerical methods for least squares problems, Philadelphia Society for Industrial and Applied Mathematics, 1996.
• [Gilbert2] Anna Gilbert, S. Muthukrishnan, and M. Strauss, Improved time bounds for near-optimal sparse Fourier representation via sampling. (Proc. SPIE Wavelets XI, San Diego, California, September 2005)
• le site http://www.dsp.ece.rice.edu/cs/ pointe sur plusieurs des articles mentionnés ainsi que des références complémentaires.
  

Durée : 4 mois minimum

Rémunération : le stage est rémunéré

Lieu : IRISA sur le campus de Beaulieu à Rennes

Equipe d'accueil : projet de recherche METISS http://www.irisa.fr/metiss/

Encadrant : Rémi Gribonval

Contact :   Rémi GRIBONVAL, Remi.Gribonval@irisa.fr, 02 99 84 25 06

Profil souhaité :

• Solides connaissances en algorithmes et structures de données
• Bon bagage en analyse matricielle et optimisation convexe
• Goût pour la programmation et les aspects mathématiques de l'informatique
• Des éléments de traitement du signal ou de l'image (analyse de Fourier ...) et/ou de probabilités et statistiques seraient un plus.
• C et/ou C++, Unix, Matlab