Random Matrices

This chapter develops a non-asymptotic theory of random matrices. It starts with a quick refresher on linear algebra, including the perturbation theory for matrices and featuring a short proof of the Davis–Kahan inequality. Three key concepts are introduced – nets, covering numbers, and packing numbers – and linked to volume and error-correcting codes. Bounds on the operator norm and singular values of random matrices are established. Three applications are given: community detection in networks, covariance estimation, and spectral clustering. Exercises explore the power method to compute the top singular value, the Schur bound on the operator norm, Hermitian dilation,Walsh matrices, the Wedin theorem on matrix perturbations, a semidefinite relaxation of the cut norm, the volume of high-dimensional balls, and Gaussian mixture models.