# Computational linear algebra

## Summary

This year we will be looking at topics in high-dimensional probability, i.e. properties of large random systems.

## Content

There are several interesting properties that become visible in large random systems like large random graphs, or random walks or random matrices etc...

For example, in such systems one observes:

- Averaging and concentration: the simplest example is the Law of Large numbers, where the average of i.i.d. random variables converges to its mean. In fact, more generally functions of many independent random variables will often be close to their expectation and one can quantitatively bound the flucatuations.

- Universality: in different large systems microscopic properties might lose their importance and some universal properties appear. The simplest example is the Central limit theorem - if you add up i.i.d. random variables with finite variance and normalize properly, the Gaussian law always appears and the fine details of initial laws of the random variables don't matter. There are much richer examples of such phenomena.

- Phase transitions: functions of several independent random variables often change their behaviour very abruptly when changing a certain parameter. For example think of the sum of n i.i.d. random variables with values +1 or -1: if the situation is symmetric, this sum is of order O(\sqrt{n}, if P(X = 1) > P(X = -1), the sum will behave like f(n) = cn and otherwise like f(n) = -cn, for some positive constant c.

We will try to look into some of these topics and the methods used to study them.

## Keywords

High-dimensional probability, concentration of measure, Gaussian processes, phase transitions, universality

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

## Recommended courses

Some interest in geometry and combinatorics might turn out to be useful

## Important concepts to start the course

Probability space, random variable and random vector, expectation, Gaussian random variables.

## Teaching methods

Lectures, exercise classes. Maybe on some topics we also try a flipped format.

## Resources

## Bibliography

A large chunk of the course is covered in Ramon van Handel "Probability in high dimension" available on his webpage.

## Notes/Handbook

There might be partial notes, though the book is excellent.

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