the matrix Bernstein inequality
/ BERN-shtine /
The matrix Bernstein inequality is the extension of scalar concentration to sums of independent RANDOM MATRICES, controlling the operator norm (largest singular value) of the deviation of such a sum from its mean. It is one of the most useful results in modern applied probability because so many high-dimensional objects are sums of independent matrices — sample covariance matrices, graph Laplacians of random graphs, matrices reconstructed from random measurements, randomized matrix sketches — and one almost always wants to know that the spectrum of the random sum is close to the spectrum of its expectation.
The statement: let S = sum_k X_k be a sum of independent, mean-zero, d-by-d (Hermitian) random matrices, each bounded in operator norm by ||X_k|| <= L almost surely. Define the matrix variance parameter v = || sum_k E[X_k^2] || (the operator norm of the sum of the second-moment matrices). Then for all t >= 0, P(||S|| >= t) <= 2d exp(-t^2 / (2(v + Lt/3))). The structure is exactly scalar Bernstein — a Gaussian regime exp(-t^2 / 2v) for small t and an exponential regime exp(-3t / 2L) for large t — but with two crucial differences. The variance is now the OPERATOR-NORM of a matrix v, capturing the worst direction of the second-moment spread, and there is an explicit DIMENSIONAL prefactor 2d in front. That d is the price of non-commutativity: the proof replaces the scalar MGF E[e^(lambda S)] with the trace of the matrix exponential E[tr exp(lambda S)], and uses the deep Lieb concavity theorem (the matrix analogue that lets you bound E[tr exp(lambda S)] by a product structure despite matrices not commuting) plus the trace inequality tr exp(A) <= d * lambda_max(exp(A)). The d appears because the operator norm is the max over d eigenvalues, and a union-bound flavor over them survives.
Read as a sample-complexity statement, matrix Bernstein says that a sum of n independent mean-zero matrices of norm at most L concentrates to within roughly sqrt(v log d) + L log d of its mean — the log d is the only trace left of the dimension, which is why these bounds are called 'nearly dimension-free' and why they are so powerful: a random matrix in dimension d concentrates almost as well as a scalar, paying only a logarithmic dimensional toll. The honest caveats. The log d factor is genuine and cannot generally be removed; it makes matrix Bernstein slightly lossy for problems where the intrinsic dimension is much smaller than d, where the intrinsic-dimension refinement (replacing d by the 'stable rank' tr(sum E[X_k^2])/v) gives the sharper bound. The almost-sure norm bound L is required for this form; unbounded summands need a matrix sub-exponential / truncation argument. And matrix Bernstein controls the operator norm of the DEVIATION, not the eigenvalues individually — for the smallest eigenvalue staying positive (covariance estimation, matrix completion) one applies it to S and reads off both ends.
Estimate a covariance matrix Sigma (d-by-d) from n iid samples x_i with ||x_i|| <= sqrt(d). The empirical covariance is (1/n) sum x_i x_i^T, a sum of independent rank-one matrices. Matrix Bernstein gives || empirical Sigma - Sigma || <= O(sqrt(||Sigma|| d log d / n) + d log d / n), so n ~ d log d samples suffice for a good operator-norm estimate — the log d is the only dimensional overhead.
A random matrix concentrates nearly as well as a scalar, paying only a log d toll.
The dimensional prefactor (the log d in the bound) is genuine; for low-intrinsic-dimension problems replace d by the stable rank for a sharper bound. The inequality needs an almost-sure operator-norm bound L; it controls the deviation's operator norm, not individual eigenvalues directly.