Fall School Marne-la-Vallée
November 16-20, 2009
Compressed sensing - Random matrices - High dimensional geometry


This Fall School discussed some interactions between compressed sensing, random matrices and high dimensional geometry. It took place on the campus of Paris-Est Marne-la-Vallée from November 16 to 20, 2009. This school was addressed to non-specialists: participation of postdocs and PhD students was strongly encouraged.

The lecture notes are merged in a book draft (comments are welcome!) [PDF]

Compressed Sensing is a quite new framework that enables approximate and exact reconstruction of sparse signals from incomplete measurements. It is strongly related to other problems of different fields such as approximation theory (diameter of sections), high dimensional geometry (neighborliness and asymptotic geometry of convex bodies), harmonic analysis (trigonometric diameter and selection of characters) and random matrices (asymptotic behavior of the largest and smallest singular values).


Five courses of 4h each:

Behavior of the largest and smallest singular values of random matrices
Speaker: Djalil Chafaï
Abstract: The extremal singular values of a matrix are very natural geometrical quantities concentrating an essential information on the invertibility and stability of the matrix. This short course of four hours aims to provide an accessible introduction to the notion of singular values of matrices and their behavior when the entries are random, including quite recent striking results from Random Matrix Theory. Gaussian models will serve as a backbone towards universality.
Preliminary lecture notes: PDF

Empirical methods and selection of characters
Speaker: Olivier Guédon
Abstract: Several problems of harmonic analysis are deeply related with the study of some empirical processes. Classical example of characters in L^2 are the Fourier or the Walsh system. In the 80's, deep results about the selection of characters that satisfy good analytic properties have been proved. We will present how these proofs are now understood, how they are connected with empirical processes and what are the connections with reconstruction of sparse signals.
Preliminary lecture notes: PDF. There are of course some omissions, that I said perhaps during the course or that I really forget. There will be later a more complete tex-file of this course.

Basic tools from empirical processes theory applied to the compress sensing problem
Speaker: Guillaume Lecué
Abstract: The RIP condition is at the heart of the problem of reconstruction of spare vectors by the basis pursuit algorithm. Up to now, no deterministic matrix has been proved to satisfy this condition. Checking if some Ensemble of random matrices satisfy this condition can be seen as a problem of empirical processes theory. We will introduce some tools used in this theory to solve this kind of problem.
Preliminary lecture notes : ChainingPDF - ComplexityPDF - ConcentrationPDF

Applications of chaining methods
Speaker: Shahar Mendelson
Abstract: I intend to present various structural results on typical coordinate projections of classes of functions. Structural results of this flavour have played a central role in empirical processes theory throughout the years and, as I will explain, are important in many statistical and geometric applications. The main theme will be to show how chaining methods allow one to obtain rather accurate information on the random geometry of a given class of functions, and explain the role of various metric structures endowed on the class have in the analysis. One application I will present is a method of controlling the supremum of an empirical process indexed by powers of functions that are very poorly bounded (for example, powers of linear functional on R^n). I will explain why this is an essential component in many problems in Asymptotic Geometric Analysis and Nonparametric Statistics and how the structural methods come into the picture.
Preliminary lecture notes: soon...

The Restricted Isometry Property (RIP) of some models of random matrices and High dimensional Geometry
Speaker: Alain Pajor
Abstract: Compressed Sensing is a quite new framework that enables approximate and exact reconstruction of sparse signals from incomplete measurements. The ideas and principles are strongly related to other problems of different fields such as approximation theory and Asymptotic Geometric Analysis. It is not in our intention to give a course on compressed sensing, but preferably to put some emphasis on interactions in particular with asymptotic geometric analysis and random matrices. The possibility to reconstruct a class of vectors is highly related to its complexity and many tools were developed in Asymptotic Geometric Analysis to analyse different concepts of complexity of subsets of Banach spaces.
Preliminary lecture notes: soon...

Practical informations

There is no registration fee. Lunches will be covered by the organization. Registration is over!


Be sure to book your hotel very early (at least a month in advance), since accomodations in Paris or near the university are difficult to find. It is recommended to select a hotel close to RER line A.

Location and directions

The Paris-Est Marne-la-Vallée Campus (Cité Descartes) encompasses among other structures the ESIEE, the ENPC (two Grandes Écoles), and the LAMA (department of mathematics of the University, Copernic building). The fallschool will take place in these three places, which are very close on the campus :

Paris-Est Marne-la-Vallée Campus

Coming from Paris by RER line A, get off the train at the station NOISY-CHAMPS (the best is to get off from the station at the head of the train when coming from Paris). See the RATP website for RER/Metro connexions and schedules. The ESIEE (ESIEE building), ENPC (ENPC building), and LAMA (Copernic building, fourth floor) are accessible in few minutes from the RER station NOISY-CHAMPS.

Capus map
Campus map

RER line A. Get off the train at station Noisy-Champs.
The best is to get off from the head of the train when coming from Paris.

General map
General map of the area


Djalil Chafaï (UMLV), Olivier Guédon (UMLV), Guillaume Lecué (CNRS & UMLV), Shahar Mendelson (ANU & Technion), Alain Pajor (UMLV)

For any help, in particular for registration or lodging, please contact our assistant:

Christiane Lafargue
Phone: +33(0)
Fax: +33(0)



Webmaster: DC .