Deviations of Random Matrices on Sets

This chapter presents the matrix deviation inequality, a uniform deviation bound for random matrices over general sets. Applications include two-sided bounds for random matrices, refined estimates for random projections, covariance estimation in low dimensions, and an extension of the Johnson–Lindenstrauss lemma to infinite sets. We prove two geometric results: the M* bound, which shows how random slicing shrinks high-dimensional sets, and the escape theorem, which shows how slicing can completely miss them. These tools are applied to a fundamental data science task – learning structured high-dimensional linear models. We extend the matrix deviation inequality to arbitrary norms and use it to strengthen the Chevet inequality and derive the Dvoretzky– Milman theorem, which states that random low-dimensional projections of high-dimensional sets appear nearly round. Exercises cover matrix and process-level deviation bounds, high-dimensional estimation techniques such as the Lasso for sparse regression, the Garnaev–Gluskin theorem on random slicing of the cross-polytope, and general-norm extensions of the Johnson–Lindenstrauss lemma.