This is a tutorial on some basic non-asymptotic methods and concepts in random matrix theory. The reader will learn several tools for the analysis of the extreme singular values of random matrices with independent rows or columns. Many of these methods sprung off from the development of geometric functional analysis since the 1970s. They have applications in several fields, most notably in theoretical computer science, statistics and signal processing. A few basic applications are covered in this text, particularly for the problem of estimating covariance matrices in statistics and for validating probabilistic constructions of measurement matrices in compressed sensing. This tutorial is written particularly for graduate students and beginning researchers in different areas, including functional analysts, probabilists, theoretical statisticians, electrical engineers, and theoretical computer scientists.

Introduction

Asymptotic and non-asymptotic regimes

Random matrix theory studies properties of N × n matrices A chosen from some distribution on the set of all matrices. As dimensions N and n grow to infinity, one observes that the spectrum of A tends to stabilize. This is manifested in several limit laws, which may be regarded as random matrix versions of the central limit theorem. Among them is Wigner's semicircle law for the eigenvalues of symmetric Gaussian matrices, the circular law for Gaussian matrices, the Marchenko–Pastur law for Wishart matrices W = A* A where A is a Gaussian matrix, the Bai–Yin and Tracy–Widom laws for the extreme eigenvalues of Wishart matrices W.