Matrix concentration and operator-norm bounds

Let X_i be independent random Hermitian d-by-d matrices with E X_i=0 and operator norm at most R almost surely, for deterministic R>0. Define v as the operator norm of ΣE X_i². Each squared Hermitian matrix is positive semidefinite, so this sum is a meaningful matrix variance proxy. It is generally different from Σ||E X_i²|| and from the largest variance of one entry, although upper bounds on it can be substituted conservatively. Degenerate v=0 makes every centered summand zero almost surely.

For t≥0, the largest-eigenvalue upper tail has prefactor d and Bernstein exponent −t²/(2(v+Rt/3)). Apply that result to both the sum and its negative to obtain an operator-norm tail with prefactor 2d. Absolute norm boundedness supplies the same R in both directions. If one had only an upper eigenvalue bound for each summand, the directed theorem would need separate care before being used for a two-sided norm. The dimension factor can make a small-threshold answer exceed one; cap it rather than interpreting it as an exact probability.

For scalar variables, independence factors exponential moments directly. Matrix exponentials do not obey exp(A+B)=exp(A)exp(B) when A and B fail to commute. Matrix concentration therefore needs trace-exponential tools and deeper inequalities rather than an entrywise repetition of scalar factorization. The theorem stated here is used as a proved primary-source result; checking its hypotheses is not a replacement proof of the noncommutative Laplace-transform step. Structured matrices with dependent entries can still satisfy the theorem if their summands are independent.

Independent random signs multiplying fixed Hermitian matrices give a transparent example. Each signed summand is centered, and its squared matrix is the deterministic square of its coefficient matrix. Variance therefore accumulates as an operator sum of those squares, even when different coefficient matrices do not commute. A common mistake would be to replace this with the square of the sum; that introduces cross terms and measures a different object. Another is to count entries as independent when one sign multiplies the entire matrix.

For an average of n summands, an operator deviation ε is the sum event at t=nε. If the variance proxy is bounded by nσ², this gives exponent −nε²/(2(σ²+Rε/3)). The dimension factor remains; it does not disappear simply because the quantity is averaged. Covariance estimation is a common application, but the rank-one observation matrices must first be centered and their almost-sure norms and variance proxy actually verified. Unbounded Gaussian observations cannot be inserted into this bounded-summand theorem without a different argument.

For rectangular or non-Hermitian Z_i, use a Hermitian dilation with off-diagonal blocks Z_i and Z_i*. Its dimension is d₁+d₂, and its square has diagonal blocks Z_iZ_i* and Z_i*Z_i. The rectangular Bernstein version uses the maximum of the two resulting variance norms and prefactor d₁+d₂. Ordinary eigenvalues of a nonsymmetric shear can all equal one while its operator norm exceeds one, so a largest-eigenvalue calculation on the original non-Hermitian matrix does not substitute for singular-value control.