Random Matrix Theory

Master’s Programme “Statistical Learning Theory”, 2nd year

The aim of this course is to provide an introduction to asymptotic and non-asymptotic methods for the study of random structures in high dimension that arise in probability, statistics, computer science, and mathematics.

Lectures: Alexey Naumov (naumovne@gmail.com).
Seminars: Leonid Iosipoi (iosipoileonid@gmail.com).

Grade Components: home assignments (40%) + individual project (20%) + oral final exam (40%).

Important dates: defence of projects – December 6, final exam – December 13.

Seminars

12.09.2019

Catalan numbers.

Recursive Definition of the Catalan numbers (balanced parentheses, Dyck paths, rooted binary trees, rooted trees). Generating function and explicit formula for the Catalan numbers.

Notes: Problem set 1.

Wigner’s Semicircular law.

Wigner matrices. Method of Moments. Moments of the Semicircular law. Proof of the Semicircular law (convergence in expectation). Generalized Wigner and Wigner type matrices.

Notes: Problem set 2.

References
[1] T. Davis. Catalan Numbers. Mathematical Circles Topics;
[2] T. Tao. Topics in Random Matrix Theory;
[3] Z. Bai, J. Silverstein. Spectral Analysis of Large Dimensional Random Matrices.

20.09.2019

Marchenko-Pastur law.

Sample covariance matrices. Moments of the Marchenko-Pastur law. Proof of the Marchenko-Pastur law (convergence in expectation).

Notes: Problem set 3.

References
[1] Z. Bai, J. Silverstein. Spectral Analysis of Large Dimensional Random Matrices;
[2] B. Valko. Lecture Notes on Random Matrices;
[3] T. Tao. Topics in Random Matrix Theory.

27.09.2019

Basic concentration inequalities and apllications.

Basic concentration inequalities: Markov and Chernoff bounds. Sub-Gaussian and sub-exponential random variables. Hoeffding bound. Johnson-Lindenstrauss embedding. Erdos-Renyi model.

Notes: Problem set 4.

References
[1] R. Vershynin. High-Dimensional Probability;
[2] M. Wainwright. High-dimensional statistics: A non-asymptotic viewpoint;
[3] S. Boucheron, G. Lugosi, P. Massart. Concentration Inequalities: A Nonasymptotic Theory of Independence.

04.10.2019

Epsilon-net argument.

Covering number of a unit sphere. Epsilon-net argument. A bound on the operator norm of a matrix with sub-Gaussian entries. Optimality of the epsilon-net argument.

Notes: Problem set 5.

References
[1] R. Vershynin. High-Dimensional Probability;
[2] M. Wainwright. High-dimensional statistics: A non-asymptotic viewpoint.

11.10.2019

Epsilon-net argument for sample covariance matrices.

Sub-Gaussian random vectors. Epsilon-net argument for sample covariance matrices.

Notes: Problem set 6.

References
[1] J. A. Tropp. An Introduction to Matrix Concentration Inequalities;
[2] R. Vershynin. High-Dimensional Probability;
[3] M. Wainwright. High-dimensional statistics: A non-asymptotic viewpoint.

18.10.2019

Comparison Method. Part I.

Lipschitz functions of Gaussian variables. Gaussian comparison inequalities (Sudakov-Fernique inequality). Bound on the expected value of the operator norm.

Notes: Problem set 7.

References
[1] R. Vershynin. High-Dimensional Probability;
[2] M. Wainwright. High-dimensional statistics: A non-asymptotic viewpoint.

15.11.2019

Comparison Method. Part II.

Lipschitz functions of Gaussian variables. Gaussian comparison inequalities (Sudakov-Fernique inequality). Bound on the expected value of the operator norm.

Notes: Problem set 7.

References
[1] R. Vershynin. High-Dimensional Probability;
[2] M. Wainwright. High-dimensional statistics: A non-asymptotic viewpoint.

22.11.2019

Bernstein-type bound

Bernstein condition for random variables. Bernstein inequality for random variables. Bernstein condition for random matrices. Bernstein inequality for random matrices.

Notes: Problem set 8.

References
[1] J. A. Tropp. An Introduction to Matrix Concentration Inequalities;
[2] R. Vershynin. High-Dimensional Probability;
[3] M. Wainwright. High-dimensional statistics: A non-asymptotic viewpoint.