Теория случайных матриц

Математические методы оптимизации и стохастики, 2 курс

Данный курс является вводным в теорию случайных матриц. Цель курса – сформировать общую картину предмета, дать представление об асимптотических и неасимототических методах, которые используются как в чистой математике, так и в различных ее приложениях.

Финальные оценки

Экзамен пройдет в среду (21 декабря) с 15:00 до 19:00 в ИППИ, ауд. 405. Приехать можно в любое время. Запишитесь, если планируете приехать, по ссылке. Если вы на экзамен не приходите, в ведомость идет ваша базовая оценка.

Мы сделали небольшой опрос о курсе. Будем рады, если вы оставите какую-нибудь обратную связь. Это не должно занять больше 3-5 минут. Все, естественно, анонимно.

Лекции: Алексей Наумов (naumovne@gmail.com).
Семинары: Леонид Иосипой (iosipoileonid@gmail.com).

Дополнительные материалы для интересующихся

Видео

Курс случайных матриц на Лекториуме. В этом курсе обсуждаются темы (типичные ансамбли, предельные теоремы для спектра), которые мы практически не затронули в нашем курсе (они больше связаны с задачами мат. физики, а не анализом данных).

Method of exchangeable pairs – доклад на одной из конференций ПреМоЛаба. Мы бегло обсудили этот метод, когда получали концентрацию для выборочной ковариационной матрицы.

How Large is the Norm of a Random Matrix? – Ramon van Handel в институте Саймонса.

Joel A. Tropp. Доклад в институте Саймонса: Часть I, Часть II, Часть III.

Книги/лекции/статьи

Кроме базовых книг и статей, ссылки на которые есть ниже, могут быть интересны:

М.Л. Мета «Случайные матрицы» – классический учебник-энциклопедия, написанная физиком. В книге разобрано много интересных приложений теории случайных матриц в физике и математике. Русского варианта нет в электронном виде, а вот английский можно найти.

T. Tao «Topics in random matrix theory» – хорошая книжка с классическими предельными теоремами.

Р. Вершинин «Introduction to the non-asymptotic analysis of random matrices» – лекции, прочитанные в школе «Random matrices - Stochastic geometry - Compressed sensing» в 2011 году. Обратите внимание на вторую половину лекции, начиная с Application: RIP for sub-gaussian matrices.

R. van Handel «Probability in High Dimension» – лекции, которые отлично дополняют Р. Вершинина.

Следующие две ссылки уже встречались ниже, но в них можно найти еще много интересного.

J. A. Tropp «An Introduction to Matrix Concentration Inequalities».
R. van Handel «Structured random matrices».

Лекции

05.09.2016

Гауссовский случай

Лемма Стейна. Моменты и хвосты гауссовских случайных величин. Гауссовские векторы: совместная плотность распределения, асимптотическая оценка сверху максимума и неравенство сравнения Судакова-Ферника.

12.09.2016

Инвариантные ансамбли матриц

Гауссовские ортогональные и унитарные ансамбли. Ансамбли Уишарта-Лагерра.

19.09.2016
03.10.2016

Предельные теоремы для спектра случайной матрицы

Преобразование Стилтьеса. Полукруговой закон Вигнера. Закон Марченко-Пастура.

10.10.2016
31.10.2016

Спектральные проекторы и ковариационная матрица

Спектральные проекторы. Верхняя оценка для мат. ожидания нормы отклонения выборочной ковариационной матрицы от истинного значения в терминах эффективного ранга.

Конспект всех лекций

07.11.2016
14.11.2016
21.11.2016

Сингулярные числа и концентрация

Наибольшее и наименьшее сингулярные числа квадратных случайных матриц. Концентрация на малых шарах, функция концентрации Леви.

Ссылки на литературу:
[1] M. Rudelson, R. Vershynin. The Littlewood–Offord problem and invertibility of random matrices;
[2] J. Bun, J.-P. Bouchaud, M. Potters. Cleaning large Correlation Matrices: tools from Random Matrix Theory.

28.11.2016

Sampling from large matrices

Семинары

Срок выполнения каждого домашнего задания: 2 недели. Оцениваться оно будет бинарно: + или –
Решенные задачи можно сдавать перед семинаром или присылать на iosipoileonid@gmail.com

05.09.2016

Суб-гауссовские случайные величины

Хвост распределения неотрицательной случайной величины. Сравнение оценки Чернова и моментных оценок. Суб-гауссовские случайные величины (эквивалентные определения и простейшие свойства).

Домашнее задание: Листок 1 (до 19.09.16)

Ссылки на литературу:
[1] T. Philips, R. Nelson. The Moment Bound Is Tighter Than Chernoff's Bound for Positive Tail;
[2] R. Vershynin. Introduction to the non-asymptotic analysis of random matrices (стр. 9-13);
[3] S. Boucheron, G. Lugosi, P. Massart. Concentration Inequalities: A Nonasymptotic Theory of Independence (стр. 29-38).

12.09.2016

Суб-экспоненциальные случайные величины

Суб-экспоненциальные случайные величины (эквивалентные определения). Cумма независимых суб-гауссовских и суб-экспоненциальных величин. Концентрация распределения хи-квадрат.

Домашнее задание: Листок 2 (до 26.09.16).

Ссылки на литературу:
[1] M. Wainwright. High-dimensional statistics: A non-asymptotic viewpoint (стр. 6-10);
[2] R. Vershynin. Introduction to the non-asymptotic analysis of random matrices (стр. 13-15);
[3] S. Boucheron, G. Lugosi, P. Massart. Concentration Inequalities: A Nonasymptotic Theory of Independence (стр. 38-42).

19.09.2016

Приложение: Вложение Джонсона-Линденштрауса

Вложение Джонсона-Линденштрауса. Сумма зависимых суб-гауссовских и суб-экпоненциальных величин. Произведение суб-гауссовских величин.

Домашнее задание: Листок 3 (до 3.10.16).

Ссылки на литературу:
[1] Набор неравенств, которые удобно иметь под рукой.
[2] M. Wainwright. High-dimensional statistics: A non-asymptotic viewpoint (стр. 11-12);
[3] S. Boucheron, G. Lugosi, P. Massart. Concentration Inequalities: A Nonasymptotic Theory of Independence (стр. 50-54).

03.10.2016

Суб-гауссовские случайные матрицы

Простейшие матричные функции и их свойства. Теорема Либа (без доказательства). Суб-гауссовские случайные матрицы и матричное неравенство Хёффдинга.

Домашнее задание: Листок 4 (до 24.10.16).

Ссылки на литературу:
[1] J. A. Tropp. User-friendly tail bounds for sums of random matrices (стр. 7-14);
[2] J. A. Tropp. From joint convexity of quantum relative entropy to a concavity theorem of Lieb.

17.10.2016

Разбор домашних задач и материала лекций.

Сравнение гауссовских векторов. Неравенство Слепяна и Судакова-Ферника. Ковариационная матрица, эффективный ранг, decoupling.

Домашнее задание: не будет.

Ссылки на литературу:
[1] В.И. Питербарг. Двадцать лекций о гауссовских процессах (стр. 13-23);
[2] R. van Handel. Structured random matrices (стр. 40-43).

31.10.2016

Суб-экспоненциальные случайные матрицы. Неравенство Бернштейна.

Суб-экспоненциальные случайные матрицы. Неравенство Хёффдинга. Неравенство Бернштейна для случайных величин и случайных матриц.

Домашнее задание: Листок 5 (до 14.11.16).

Ссылки на литературу:
[1] J. A. Tropp. User-friendly tail bounds for sums of random matrices (стр. 23-27);
[2] M. Wainwright. High-dimensional statistics: A non-asymptotic viewpoint (стр. 8-10).

07.11.2016

Приложения: свойства графа Эрдеша-Реньи.

Концентрация степеней вершин графа Эрдеша-Реньи с большой вероятностью. Теорема Гершгорина. Лапласиан графа. Связность графа Эрдеша-Реньи.

Домашнее задание: Листок 6 (до 21.11.16).

Ссылки на литературу:
[1] J. A. Tropp. An Introduction to Matrix Concentration Inequalities (стр. 73-76);
[2] R. Vershynin. High-Dimensional Probability (стр. 25-27);
[3] J. Kelner. Topics in Theoretical Computer Science. Lecture Notes, MIT. Лекция 1 Лекция 2;
[4] А.М. Райгородский. Модели случайных графов и их применения.

14.11.2016

Оценки «с большой верятностью» для норм.

Простейшие матрицы. Неравенство Хёффдинга и оценки «с большой верятностью». Симметризация. Аппроксимация с помощью эпсилон-сети.

Домашнее задание: Листок 7 (до 01.12.16) \\ решать все задачи совсем не обязательно.

Ссылки на литературу:
[1] J. A. Tropp. User-friendly tail bounds for sums of random matrices (стр. 14-17);
[2] R. Vershynin. High-Dimensional Probability (стр. 83-93).

21.11.2016

Оценка ковариационной матрицы.

Суб-гауссовские случайные векторы. Близость выборочной ковариационной матрицы в операторной норме «с большой верятностью» для суб-гауссовских векторов.

Домашнее задание: Листок 8 (до 05.12.16)

Ссылки на литературу:
[1] J. A. Tropp. An Introduction to Matrix Concentration Inequalities (стр. 90-91);
[2] R. Vershynin. High-Dimensional Probability (стр. 98-102).

28.11.2016

Приложения: поиск сообществ в социальных сетях.

Stochastic Block Model. Spectral Clustering.

Домашнее задание: не будет.

Ссылки на литературу:
[1] R. Vershynin. High-Dimensional Probability (стр. 93-97).