Compressed Sensing

Objective

Ce cours abordera le paradigme de la statistique en grande dimension principalement autour de trois
thématiques :
1. Compressed sensing: problème de reconstruction exacte et approchée d'un signal de grande dimen-
sion à partir d'un petit nombre de mesures linéaires de ce vecteur sachant qu'il a un petit support;
2. 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;
3. détection de communautés dans les graphes: trouver les sous-graphes de forte densité dans des
'grands' graphes.

Planning

Le problème de Compressed Sensing sera utilisé comme le principale vecteur pédagogique pour l'apprentissage
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. 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.

References

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.