Concentration without Independence

This chapter explores methods of concentration that do not rely on independence. We introduce the isoperimetric approach and discuss concentration inequalities across a variety of metric measure spaces – including the sphere, Gaussian space, discrete and continuous cubes, the symmetric group, Riemannian manifolds, and the Grassmannian. As an application, we derive the Johnson–Lindenstrauss lemma, a fundamental result in dimensionality reduction for high-dimensional data. We then develop matrix concentration inequalities, with an emphasis on the matrix Bernstein inequality, which extends the classical Bernstein inequality to random matrices. Applications include community detection in sparse networks and covariance estimation for heavy-tailed distributions. Exercises explore binary dimension reduction, matrix calculus, additional matrix concentration results, and matrix sketching.