Probability in high dimensions. Math 709, Fall 2012

Instructor: Roman Vershynin
E-mail: romanv "at" umich "dot" edu.
Class will meet T,Th 11:40 am - 1:00 pm in 3088 East Hall.

Prerequisites: Familiarity with basic probability theory (as covered e.g. in Math/Stats 525) and basic functional analysis (an elementary knowledge of Hilbert and normed spaces and linear operators).

Description

The is a course on modern problems and methods in high-dimensional probability theory and its applications. The course will consist of three connected parts: 1) concentration of measure, 2) non-asymptotic analysis of random matrices, and 3) stochastic processes and geometric probability in high dimensions. The emphasis will be given to applications across statistics (covariance estimation), signal processing (compressed sensing), information theory (dimension reduction), and computer science (low-rank approximations of matrices and graph sparsification).

1. The first part of this course will explore the concentration of measure phenomenon. We will start from the classical deviation inequalities for sums of independent random variables and proceed to concentration of Lipschitz functions on the sphere, hypercube, and some discrete spaces. This is the basis for the development of dimension reduction methods (starting from Johnson-Lindenstrauss Lemma).

2. The second part will develop a non-asymptotic analysis of random matrices. This will start with a modern treatment of sums of independent random matrices. We will proceed with the spectral analysis of random matrices with independent rows and columns, focusing on their extreme singular values. We will study analytic methods like Stieltjes transform, geometric methods including covering arguments, and probabilistic tools involving Gaussian processes and decoupling. These methods will be used for the development of compressed sensing, the modern paradigm in signal processing that allows one to recover structured signals from few measurements. We also discuss applications for random sampling from matrices (i.e. estimating a matrix from a sample of its entries) and for matrix and graph sparsification.

3. The last part of the course will develop probabilistic methods for geometric problems in high dimension; this will cover some basics of geometric functional analysis. The focus will be on the geometry of high dimensional convex sets, either random or deterministic, and their random sections and projections. We will discuss John's decompositions, Kolmogorov and Gelfand widths, volume ratio and Kashin's splittings, Dvoretzky-Milman theorems on Euclidean sections, and metric entropy. Along the way, we will develop more methods for stochastic processes (Sudakov and Dudley inequalities). These developments provide intuition and techniques for dimension reduction and compressed sensing.

Textbook. There is no required textbook. Relevant texts (surveys and research papers) will be posted online.

Grading: There will be no exams. The grade will be determined by an the oral presentation of a research paper or an original project.

Course webpage: http://www-personal.umich.edu/~romanv/teaching/2012-13/709/709.html