the matrix Chernoff inequality
/ CHER-nof /
The matrix Chernoff inequality controls the extreme EIGENVALUES — the smallest and the largest — of a sum of independent, positive-semidefinite random matrices. Where matrix Bernstein bounds the operator norm of a mean-zero deviation, matrix Chernoff is the tool for PSD sums where what you care about is that the random sum stays well-conditioned: that its smallest eigenvalue does not collapse to zero (so the sum is invertible/the matrix is full rank) and its largest eigenvalue does not blow up. This is the matrix analogue of the scalar Chernoff bound for sums of non-negative bounded variables.
The statement: let X_1, ..., X_n be independent, positive-semidefinite, d-by-d random matrices with each ||X_k|| <= L almost surely, and let S = sum_k X_k with mean matrix M = E[S]. Write mu_min = lambda_min(M) and mu_max = lambda_max(M) for the extreme eigenvalues of the expected sum. Then the smallest eigenvalue obeys, for eps in [0,1), P(lambda_min(S) <= (1 - eps) mu_min) <= d * (e^(-eps) / (1-eps)^(1-eps))^(mu_min / L), and the largest eigenvalue obeys, for eps >= 0, P(lambda_max(S) >= (1 + eps) mu_max) <= d * (e^(eps) / (1+eps)^(1+eps))^(mu_max / L). The exponents (e^(-eps)/(1-eps)^(1-eps)) and its sibling are exactly the scalar Chernoff exponents; the only matrix overhead is again the dimensional prefactor d. The proof follows the same trace-MGF / Lieb-concavity machine as matrix Bernstein, but tailored to PSD matrices, where one can take a one-sided exponential and read off the eigenvalue bounds directly. As with matrix Bernstein, the dimension enters only through the factor d, so the bound is again nearly dimension-free: roughly, lambda_min(S) >= mu_min - O(sqrt(L mu_min log d)) and lambda_max(S) <= mu_max + O(sqrt(L mu_max log d)).
The killer applications are spectral. Matrix Chernoff is the standard tool for proving that a random graph's Laplacian is well-conditioned (spectral sparsification: a graph sparsified by sampling edges with the right probabilities preserves the spectrum, which is what powers fast Laplacian solvers), that a random sample of rows of a matrix forms a good subspace embedding (column subset selection, leverage-score sampling), and that a sum of independent rank-one outer products has full rank. The honest caveats parallel matrix Bernstein. The bound needs the summands to be PSD and uniformly bounded in operator norm by L; it is one-sided per inequality, and the smallest-eigenvalue bound degrades when mu_min / L is small — that ratio is the effective 'number of samples per dimension', and you genuinely need mu_min >= L log d for the smallest eigenvalue to be controlled, which is the rigorous reason oversampling by a log d factor is necessary in spectral sparsification and leverage-score sampling. The dimensional log d, again, is real and only removable down to the intrinsic dimension.
Spectral sparsification: sample m edges of a graph with n vertices, each edge included with probability proportional to its effective resistance. Each sampled, reweighted edge contributes a PSD rank-one matrix to the normalized Laplacian, whose expectation is the identity on the relevant subspace. Matrix Chernoff shows that m = O(n log n / eps^2) samples keep all eigenvalues within (1 +/- eps), so the sparse graph has the same Laplacian spectrum as the original up to eps.
Matrix Chernoff keeps the smallest and largest eigenvalues of a PSD sum under control.
Requires PSD summands with an almost-sure norm bound L; the smallest-eigenvalue control genuinely needs mu_min >= L log d, which is why oversampling by log d is necessary (not an artifact). It bounds extreme eigenvalues one-sidedly, not the operator norm of a mean-zero deviation — use matrix Bernstein for that.