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...
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.
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 :
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.
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 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)1.60.95.75.20
Fax: +33(0)1.60.95.75.45
christiane.lafargue@univ-mlv.fr