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...

**Preliminary schedule**(**detailed version**)**Experimental booklet****Experimental poster****List of participants**

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 :

`Mon 2009-11-16:`ESIEE building (amphi 110 main floor) + lunch at ESIEE`Tue 2009-11-17:`ESIEE building (amphi 110 main floor) + lunch at ESIEE`Wed 2009-11-18:`ESIEE building (amphi 110 main floor) + lunch at ESIEE`Thu 2009-11-19:`ENPC building (amphi Navier) + buffet at LAMA (Copernic building fourth floor)`Fri 2009-11-20:`ESIEE building (amphi 110 main floor) + lunch at ESIEE

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.**

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

- Université Paris-Est Marne-la-Vallée
- École doctorale MSTIC
- CNRS
- ESIEE
- Projet ANR GranMa (Grandes Matrices Aléatoires ANR-08-BLAN-0311-01)
- École des ponts (ENPC)

- Compressive Sensing: The Big Picture
- Compressive Sensing Resources (Rice University)
- Compressive sensing on Wikipedia
- Compressed sensing on the blog of Terry Tao
- Emmanuel Candès HomePage
- Ronald DeVore lecture notes on foundations of compressed sensing (home page of Albert Cohen)
- Slides and lecture notes on compressive sensing by Holger Rauhut
- Gabriel Peyré HomePage