**Lecturer** : Justin Romberg (Georgia Institute of Technology, Atlanta)

**Outline of the school :**

“The dogma of signal processing maintains that a signal must be sampled at a rate at least twice its highest frequency in order to be represented without error. However, in practice, we often compress the data soon after sensing, trading off signal representation complexity (bits) for some error (consider JPEG image compression in digital cameras, for example). Clearly, this is wasteful of valuable sensing resources. Over the past few years, a new theory of “compressive sensing” has begun to emerge, in which the signal is sampled (and simultaneously compressed) at a greatly reduced rate.

Compressive sensing is also referred to in the literature by the terms: compressed sensing, compressive sampling, and sketching/heavy-hitters.” [by courtesy of: http://dsp.rice.edu/cs]

- Basis decompositions and frames (3-4 hours)
- fundamentals of basis and frame decompositions
- the discrete cosine transform and applications to image/video compression
- the lapped orthogonal transform
- wavelets
- thresholding for noise reduction

- Sparsest decomposition from a dictionary (3-4 hours)
- omp and basis pursuit for selecting atoms
- uncertainty principles and sparsest decomposition
- the “spikes+sines” dictionary
- general unions of orthobases

- Introduction to compressive sampling and applications (2 hours)
- Recovering sparse vectors from linear measurements (6 hours/ 1 day)
- review of classical least-squares theory: the svd, pseudo-inverse, stability analysis, regularization
- sparse recovery conditions: l1 duality, sparsest decomposition revisited (with random support)
- the restricted isometry property and sparse recovery : l1 for perfect recovery from noise-free measurements,

l1 stability, l2 stability

- Random matrices are restricted isometries (2 hours)
- Optimization (6 hours / 1 day)
- conjugate gradients
- log-barrier methods
- first-order l1 solvers
- greedy algorithms and iterative thresholding
- recursive least-squares
- the Kalman filter
- dynamic l1 updating

- Low-rank recovery (2 hours)

**Dates** : 9-13/01/2012

**Correspondant local** : Paulo Goncalves