Analysis of Matrix Data

Objectif

Le matériel de cours est disponible à la page web :

https://lecueguillaume.github.io/2015/10/08/compressed_sensing_course/

L’objectif de ce cours est d’étudier des problèmes de statistiques en grandes dimensions afin de dégager trois idées fondamentales de cette thématique qui pourront par la suite être appliquées dans de nombreux autres problèmes liés aux sciences des données. Nous énonçons brièvement ces principes :

•  Un grand nombre de données réelles appartiennent à des espaces de grandes dimensions dans lesquels les méthodes classiques de statistiques sont inefficaces (cf. fléau de la dimension). Néanmoins ces données sont pour la plupart d’entre elles structurées. Si bien que la “vraie” dimension du problème n’est plus celle de l’espace ambiant mais plutôt celle de la structure qui contient l’information utile des données. On parle de données structurées ou parcimonieuses. La construction de bases ou dictionnaires permettant de révéler les structures de faible dimension de ces données est une composante importante de la statistique en grande dimension.
•  En première approche, la recherche de ces structures de faible dimension semble nécessiter le lancement d’une recherche combinatoire dans un espace de grande dimension. De telles procédures ne peuvent pas être utilisées en pratique. Une composante importante de la statistique en grande dimension est alors de proposer et d’analyser des algorithmes qui peuvent être implémentés même dans des espaces de grande dimension. Pour cela, deux approches ont reçu une attention particulière : la relaxation convexe (couplé à la boîte à outils de l’optimisation convexe) et les algorithmes itératifs qui permettent de résoudre parfois des problèmes d’optimisation non-convexe.
•  Finalement, la troisième composante est le rôle joué par l’aléatoire dans la statistique en grande dimension. Il s’avère que les structures de faibles dimensions sont généralement révélées par des objets aléatoires et que, jusqu’à maintenant, on ne sait pas exhiber ces structures à l’aide de mesures déterministes aussi efficacement que le font, par exemple, les matrices aléatoires.

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 :

•  Compressed sensing: 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.

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

1. concentration de variables aléatoires et calcul de complexité;

2. méthodes et analyse d’algorithmes en optimisation convexe.

Les séances de travaux pratiques informatiques s’effectueront avec le langages Python. On mettra particulièrement l’accent sur les librairies classiques en science des données: sklearn, cvxopt et networkx.

A l’issue de ce cours, les étudiants doivent être capable de

• identifier les propriétés computationnelle de certains problèmes d’optimisation, en particulier, identifier les problèmes computationnelle difficile,
•  trouver des relaxation convexes pour ces problèmes d’optimisation (non-convexe)
• comprendre le rôle de l’aléatoire pour ces problèmes, en particulier pour construire des vecteurs de mesures adéquates
• utiliser les problèmes de compressed sensing, matrice completion et de détection de communauté comme des problèmes standard
• construire des algorithmes permettant d’approcher les solutions des problèmes d’optimisation “convexifiés”.

Plan

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 (ou 4) séances de cours, 2 séances d’exercices et 1 (ou 2) séances de pratiques informatiques (le temps consacré en TP dépendra du goût des élèves au fil du cours). 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.

Références

Venkat Chandrasekaran, Benjamin Recht, Pablo A. Parrilo, and Alan S. Willsky. The convex geometry of linear inverse problems. Found. Comput. Math., 12(6):805{849, 2012.

Simon Foucart. A simple proof of kashin decomposition theorem. Technical report, Drexel University, 2012.

Olivier Guédon and Roman Vershynin. Community detection in sparse networks via grothendieck's inequality. Technical report, 2014.

Trevor Hastie, Rahul Mazumder, Jason D. Lee, and Reza Zadeh. Matrix completion and low-rank svd via fast alternating least squares. Technical report, Statistics Department and ICME Stanford University, 2014.

Felix Krahmer and Rachel Ward. New and improved Johnson-Lindenstrauss embeddings via the restricted isometry property. SIAM J. Math. Anal., 43(3):1269{1281, 2011.

Emile Richard, Guillaume Obozinski, and Jean-Philippe Vert. Tight convex relaxations for sparse matrix factorization. Technical report, 2012.

Ruslan Salakhutdinov, Andriy Mnih, and Georgey Hinton. Restricted boltzmann machines for collaborative filtering. Technical report, Toronto University, 2010.

Joel A. Tropp. Convex recovery of a structured signal from independent random linear measurements. Technical report, To appear in Sampling Theory, a Renaissance, 2014.