Computational linear algebra

MATH-496 / 5 credits

Teacher:

Language: English

Remark: pas donné en 2024-25

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
  • Type: optional
  • 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
  • Type: optional
  • 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
  • Type: optional

Reference week

Related courses

Results from graphsearch.epfl.ch.