Quadratic Forms, Symmetrization, and Contraction

This chapter introduces several basic tools in high-dimensional probability: decoupling, concentration for quadratic forms (the Hanson–Wright inequality), symmetrization, and contraction. These techniques are illustrated through estimates of the operator norm of a random matrix. This is applied to matrix completion, where the goal is to recover a low-rank matrix from a random subset of its entries. Exercises explore variants of the Hanson–Wright inequality, mean estimation, concentration of the norm for anisotropic random vectors, distances to subspaces, graph cutting, the concept of type in normed spaces, non-Euclidean versions of the approximate Caratheodory theorem, and covariance estimation.