DATA906 - Introduction to compressive sensing

Un cours de statistiques en grande dimension peut donc couvrir plusieurs pans des mathématiques dont la théorie de l’approximation, l’optimisation convexe et les probabilités. Dans ce cours, nous étudierons principalement l’aspect algorithmique et probabiliste de cette théorie. La théorie de l’approximation ne sera que très brièvement abordée au travers de l’exemple des images.

Ce cours abordera le paradigme de la statistique en grande dimension principalement autour de trois thématiques :

problème de reconstruction exacte et approchée d’un signal de grande dimension à partir d’un petit nombre de mesures linéaires de ce vecteur sachant qu’il a un petit support;
complétion de matrice / système de recommandation : comment compléter une matrice à partir de l’observation d’un petit nombre de ses entrées sachant que cette matrice est de faible rang;
détection de communauté dans les graphes : trouver les sous-graphes de forte densité dans des ‘grands’ graphes.
Nous abordons donc le problème de la statistique en grande dimension au travers de trois objets/ types de données clefs pour la science des données : les vecteurs de grande dimension mais parcimonieux, les matrices de grande taille mais de faible rang et finalement, les graphes de ‘grande’ taille dont les noeuds sont organisés en communautés.

Le problème de Compressed Sensing sera utilisé comme le principale vecteur pédagogique pour l’apprentissage des trois idées clefs de la statistique en grandes dimensions mentionnés précédemment. On y consacrera donc 8 séances divisées comme suit : 5 séances de cours, 2 séances d’exercices et 1 séances de pratiques informatiques. Puis nous consacrerons les 4 dernières séances aux problèmes de complétion de matrices et de détection de communautés: 1 séance de cours/exercices et 1 séance d’informatique pour chacune des deux thématiques.

D’un point de vue des techniques mathématiques nous mettrons l’accent sur les thématiques suivantes :

concentration de variables aléatoires et calcul de complexité;
méthodes et analyse d’algorithmes en optimisation convexe.
Les séances de travaux pratiques informatiques s’effectueront en Python. On mettra particulièrement l’accent sur les librairies sklearn, cvxopt/cvxpy et networkx.

Prérequis

Pas de prérequis à l’exception des connaissances élémentaires en algèbre des matrices, analyse convexe et probabilités.

Note finale

1 mémoire sous forme de texte ou de notebook python commenté + soutenance par binôme.