High dimensional probability. Math 626, Winter 2016

Instructor: Roman Vershynin
Office: 3064 East Hall
E-mail: romanv "at" umich "dot" edu

Class meets: Tu, Th 10:10 - 11:30 am in 3096 East Hall.

Office hours: Tu, Th 1:30 - 3:00 pm in 3064 East Hall.

Prerequisites: Graduate probability theory, undergraduate linear algebra, familiarity with basic notions about Hilbert and normed spaces.


This is a course in high-dimensional probability theory and its applications. The goal is to expose graduate students to basic probabilistic methods and ideas that go beyond standard probability curriculum and are essential for research in modern mathematics and other quantitative areas.

The course will cover basic concentration inequalities (for sums of independent random variables, vectors, matrices, Lipschitz functions, and martingales), geometric and combinatorial theory of stochastic processes (Gaussian processes via metric entropy: Sleipan, Dudley, Sudakov inequalities; empirical processes via Vapnik-Chervonenkis dimension), and various applications in high-dimensional settings (examples include dimension reduction, compressed sensing, random matrices, networks, covariance estimation, regression).

Textbook. Simultaneously with teaching this course, I will be writing a textbook on the same material. Here you can find the current working draft of the book:

Additionally, the following references cover some of the material, and they are available online:
  1. Y. Plan, Probability in high dimensions, graduate course at UBC.
  2. R. Vershynin, Introduction to the non-asymptotic analysis of random matrices. Compressed sensing, 210--268, Cambridge Univ. Press, Cambridge, 2012.
  3. R. van Handel, Probability in high dimension, ORF 570 Lecture notes, Princeton University, 2014.
  4. D. Chafai, O. Guedon, G. Lecue, A. Pajor, Interactions between compressed sensing, random matrices and high dimensional geometry, preprint.
  5. R. Vershynin, Lectures in geometric funcitonal analysis.

Grading: The base grade will be B if you attend a majority of the classes. It will be adjusted upwards according to the quality and quantity of your homework. There will be no exams.

Homework: Homework will be assigned from the draft of R. Vershynin's book on high dimensional probability. An estimated difficulty of each exercise is shown there; it is a number between 1 and 10. To earn grade A- or A, you should make a good progress on a majority (about 80%) of exercises with difficulty below 6. Better performance, and especially good progress on more difficult problems, will result in an A+.

Homework 1, due Thursday, February 25. From this version of the book: Exercises 2.2.6, 2.3.2, 2.3.5, 2.3.6, 2.4.2, 2.4.3, 2.5.3, 2.5.4, 2.6.7, 3.1.3, 3.1.4, 3.2.2, 3.3.2, 3.4.3, 3.4.4, 3.4.6, 3.4.8, 3.4.9.

Homework 2, due Tuesday, March 29. From this version of the book: Exercises 2.5.8, 4.2.6, 4.2.7, 4.3.2, 4.5.3, 4.6.4, 5.1.8, 5.2.3, 5.2.5, 5.3.3, 5.5.1, 5.5.2, 5.7.4, 6.2.3, 6.2.7, 6.3.3, 6.3.6, 6.4.4.

Homework 3, due Thursday, April 14. From this version of the book: Exercises 7.1.7, 7.3.11, 7.3.12, 7.4.4, 7.4.5, 7.5.5, 7.6.4, 7.7.3, 7.7.6, 7.7.11, 7.7.13, 7.7.14, 7.8.3, 7.8.4, 7.9.4, 7.9.6, 7.9.12

Course webpage: http://www-personal.umich.edu/~romanv/teaching/2015-16/626/626.html