Rechercher

sur ce site


Accueil du site > Résumés des séminaires > Labo > Sur la propriété d’isométrie restreinte de la matrice de Fourier aléatoire

Sur la propriété d’isométrie restreinte de la matrice de Fourier aléatoire

Le compressed sensing est un problème de traitement de données où les étapes d’acquisition et de compression se font en même temps. Une telle procédure peut permettre de grands gains de performances en terme de stockage ainsi que de coût/vitesse d’acquisition si la donnée stockée/observée permet la reconstruction exacte du signal d’origine. Une telle reconstruction ne peut être efficace pour tous signaux et nécessite donc que les signaux d’origine satisfassent certaines propriétés. En compressed sensing, on s’intéresse surtout à des propriété de parcimonie (ou approximativement parcimonieuses). C’est-à-dire, on suppose que le signal d’origine peut être décrit avec seulement quelques paramètres dans une base précédemment choisie (c’est-à-dire les signaux sur lesquels on travaille ont un petit support dans une certaine base).

Dans cet exposé, on se limitera au cas où les données observées/acquises sont un petit nombre de coefficients de Fourier du signal d’origine et où les signaux d’origines sont parcimonieux dans la base canonique de C^N. Le problème mathématique s’énonce donc de la manière suivante : sachant qu’on observe m coefficients de Fourier d’un signal x de grande dimension N mais de petit support de taille s, quelles sont les conditions sur les trois paramètres s,m et N et quelles sont les m fréquences de Fourier à transmettre de telle sorte qu’il soit possible de reconstruire exactement x seulement à partir de ces m coefficients de Fourier ?

Dans cet exposé, on montrera qu’une sélection aléatoire des fréquences à transmettre permet de prendre m (le nombre de mesures) de l’ordre de s (la taille des supports des signaux) à des termes logarithmiques près. On rappellera les connections entre ce problème et d’autres problèmes concernant les matrices aléatoires, les sections presque euclidiennes de la boule unité associée à la norme l1 et le "principe d’incertitude discret" (si le temps le permet on mentionnera aussi les connections avec les polytopes symétriques convexes, les codes correcteurs d’erreur et certains problèmes d’interpolation). On rappellera brièvement la preuve de Rudelson et Vershynin [RV montrant qu’avec grande probabilité, il suffit de m=s log^4 N mesures pour reconstruire tout vecteurs s sparse. La conjecture est qu’en fait on aurait seulement besoin de m=s log N mesures. On précisera quelles sont les sources potentielles des pertes logarithmiques dans l’argument de [RV].

Finalement, dans une dernière partie, on présentera les principales différences entre les matrices purement aléatoires (comme les matrices à entrées iid Gaussiennes) et les matrices de Fourier aléatoires (sous-matrice de la matrice de Fourier discrète obtenues par extraction aléatoire de ses lignes).


CMAP UMR 7641 École Polytechnique CNRS, Route de Saclay, 91128 Palaiseau Cedex France, Tél: +33 1 69 33 46 23 Fax: +33 1 69 33 46 46