# Computational linear algebra

MATH-496 / **5 credits**

**Teacher: **

**Language:** English

**Remark:** pas donné en 2022-2023

## Summary

This is an introductory course to the concentration of measure phenomenon - random functions that depend on many random variables tend to be often close to constant functions.

## Content

Concentration of measure plays an important role in probability theory, statistics, probabilistic combinatorics, analysis etc, but is also on its own a beautiful topic. The basic examples of the concentration of measure phenomena are the following:

1) The visual distance of a N-dimensional unit sphere is only of order N^{-0.5}: or in other words more than 99% of the measure on the sphere lies at the distance of O(N^{-0.5}) of a fixed hyperplane through the origin.

2) The suprema of a centred Gaussian process G(t) even with a possibility infinite index set T is always concentrated around its expected value with a Gaussian tail that only depends on the highest variance among the Gaussians G(t).

In this course we will try to understand these two slightly puzzling examples and related phenomena.

Topics discussed include: suprema of Gaussian and empirical processes, log-Sobolev inequalities and the entropy method, isoperimetry and other geometrical examples.

This course is accessible to motivated 3rd year students.

## Keywords

log-Sobolev inequalities, isoperimetry, entropy

## Learning Prerequisites

## Required courses

Mathematics Bachelor's level knowledge of analysis, linear algebra and probability (for example, the Bloc "Science de Base" in EPFL Mathematics Bachelor's program).

## Teaching methods

Lectures + exercise classes

## Assessment methods

Oral exam

Dans le cas de l'art. 3 al. 5 du Règlement de section, l'enseignant décide de la forme de l'examen qu'il communique aux étudiants concernés.

## Resources

## Bibliography

- R.van Handel's lecture notes on "Probability in high dimension" (available on his webpage)
- "Concentration Inequalities: A Nonasymptotic Theory of Independence" by S. Boucheron, G. Lugosi and P. Massart.

## Ressources en bibliothèque

## In the programs

**Semester:**Spring**Exam form:**Oral (summer session)**Subject examined:**Computational linear algebra**Lecture:**2 Hour(s) per week x 14 weeks**Exercises:**2 Hour(s) per week x 14 weeks

**Semester:**Spring**Exam form:**Oral (summer session)**Subject examined:**Computational linear algebra**Lecture:**2 Hour(s) per week x 14 weeks**Exercises:**2 Hour(s) per week x 14 weeks

**Semester:**Spring**Exam form:**Oral (summer session)**Subject examined:**Computational linear algebra**Lecture:**2 Hour(s) per week x 14 weeks**Exercises:**2 Hour(s) per week x 14 weeks

## Reference week

Mo | Tu | We | Th | Fr | |

8-9 | |||||

9-10 | |||||

10-11 | |||||

11-12 | |||||

12-13 | |||||

13-14 | |||||

14-15 | |||||

15-16 | |||||

16-17 | |||||

17-18 | |||||

18-19 | |||||

19-20 | |||||

20-21 | |||||

21-22 |