Matrix Chernoff bound

For certain applications in linear algebra, it is useful to know properties of the probability distribution of the largest eigenvalue of a finite sum of random matrices. Suppose formula_1 is a finite sequence of random matrices. Analogous to the well-known Chernoff bound for sums of scalars, a bound on the following is sought for a given parameter "t":
The following theorems answer this general question under various assumptions; these assumptions are named below by analogy to their classical, scalar counterparts. All of these theorems can be found in , as the specific application of a general result which is derived below. A summary of related works is given.
Matrix Gaussian and Rademacher series.
Self-adjoint matrices case.
Consider a finite sequence formula_3 of fixed,
self-adjoint matrices with dimension formula_4, and let formula_5 be a finite sequence of independent standard normal or independent Rademacher random variables.
Then, for all formula_6,
where
Rectangular case.
Consider a finite sequence formula_9 of fixed, self-adjoint matrices with dimension formula_10, and let formula_5 be a finite sequence of independent standard normal or independent Rademacher random variables.
Define the variance parameter
Then, for all formula_6,
Matrix Chernoff inequalities.
The classical Chernoff bounds concern the sum of independent, nonnegative, and uniformly bounded random variables.
In the matrix setting, the analogous theorem concerns a sum of positive-semidefinite random matrices subjected to a uniform eigenvalue bound.
Matrix Chernoff I.
Consider a finite sequence formula_1 of independent, random, self-adjoint matrices with dimension formula_4.
Assume that each random matrix satisfies
almost surely.
Define
Then
Matrix Chernoff II.
Consider a sequence formula_21 of independent, random, self-adjoint matrices that satisfy
almost surely.
Compute the minimum and maximum eigenvalues of the average expectation,
Then
The binary information divergence is defined as
for formula_27.
Matrix Bennett and Bernstein inequalities.
In the scalar setting, Bennett and Bernstein inequalities describe the upper tail of a sum of independent, zero-mean random variables that are either bounded or subexponential. In the matrix
case, the analogous results concern a sum of zero-mean random matrices.
Bounded case.
Consider a finite sequence formula_1 of independent, random, self-adjoint matrices with dimension formula_4.
Assume that each random matrix satisfies
almost surely.
Compute the norm of the total variance,
Then, the following chain of inequalities holds for all formula_32:
The function formula_34 is defined as formula_35 for formula_36.
Subexponential case.
Consider a finite sequence formula_1 of independent, random, self-adjoint matrices with dimension formula_4.
Assume that 
for formula_40.
Compute the variance parameter,
Then, the following chain of inequalities holds for all formula_32:
Rectangular case.
Consider a finite sequence formula_44 of independent, random, matrices with dimension formula_10.
Assume that each random matrix satisfies
almost surely.
Define the variance parameter
Then, for all formula_32
holds.
Matrix Azuma, Hoeffding, and McDiarmid inequalities.
Matrix Azuma.
The scalar version of Azuma's inequality states that a scalar martingale exhibits normal concentration about its mean value, and the scale for deviations is controlled by the total maximum squared range of the difference sequence.
The following is the extension in matrix setting.
Consider a finite adapted sequence formula_1 of self-adjoint matrices with dimension formula_4, and a fixed sequence formula_3 of self-adjoint matrices that satisfy
almost surely.
Compute the variance parameter
Then, for all formula_32
The constant 1/8 can be improved to 1/2 when there is additional information available. One case occurs when each summand formula_57 is conditionally symmetric.
Another example requires the assumption that formula_57 commutes almost surely with formula_59.
Matrix Hoeffding.
Placing addition assumption that the summands in Matrix Azuma are independent gives a matrix extension of Hoeffding's inequalities.
Consider a finite sequence formula_1 of independent, random, self-adjoint matrices with dimension formula_4, and let formula_3 be a sequence of fixed self-adjoint matrices.
Assume that each random matrix satisfies
almost surely.
Then, for all formula_32
where
An improvement of this result was established in :
for all formula_32
where
Matrix bounded difference (McDiarmid).
In scalar setting, McDiarmid's inequality provides one common way of bounding the differences by applying Azuma's inequality to a Doob martingale. A version of the bounded differences inequality holds in the matrix setting.
Let formula_70 be an independent, family of random variables, and let formula_71 be a function that maps formula_72 variables to a self-adjoint matrix of dimension formula_4.
Consider a sequence formula_3 of fixed self-adjoint matrices that satisfy
where formula_76 and formula_77 range over all possible values of formula_78 for each index formula_79.
Compute the variance parameter
Then, for all formula_32
where formula_83.
An improvement of this result was established in (see also ):
for all formula_32
where formula_83 and
formula_8
Survey of related theorems.
The first bounds of this type were derived by . Recall the theorem above for self-adjoint matrix Gaussian and Rademacher bounds:
For a finite sequence formula_3 of fixed,
self-adjoint matrices with dimension formula_4 and for formula_5 a finite sequence of independent standard normal or independent Rademacher random variables, then 
where
Ahlswede and Winter would give the same result, except with 
By comparison, the formula_94 in the theorem above commutes formula_95 and formula_96; that is, it is the largest eigenvalue of the sum rather than the sum of the largest eigenvalues. It is never larger than the Ahlswede–Winter value (by the norm triangle inequality), but can be much smaller. Therefore, the theorem above gives a tighter bound than the Ahlswede–Winter result.
The chief contribution of was the extension of the Laplace-transform method used to prove the scalar Chernoff bound (see Chernoff bound#Theorem for additive form (absolute error)) to the case of self-adjoint matrices. The procedure given in the derivation below. All of the recent works on this topic follow this same procedure, and the chief differences follow from subsequent steps. Ahlswede & Winter use the Golden–Thompson inequality to proceed, whereas Tropp uses Lieb's Theorem.
Suppose one wished to vary the length of the series ("n") and the dimensions of the
matrices ("d") while keeping the right-hand side approximately constant. Then
n must vary approximately as the log of "d". Several papers have attempted to establish a bound without a dependence on dimensions. Rudelson and Vershynin give a result for matrices which are the outer product of two vectors. provide a result without the dimensional dependence for low rank matrices. The original result was derived independently from the Ahlswede–Winter approach, but proves a similar result using the Ahlswede–Winter approach.
Finally, Oliveira proves a result for matrix martingales independently from the Ahlswede–Winter framework. Tropp slightly improves on the result using the Ahlswede–Winter framework. Neither result is presented in this article.
Derivation and proof.
Ahlswede and Winter.
The Laplace transform argument found in is a significant result in its own right:
Let formula_97 be a random self-adjoint matrix. Then
To prove this, fix formula_99. Then
The second-to-last inequality is Markov's inequality. The last inequality holds since formula_101. Since the left-most quantity is independent of formula_102, the infimum over formula_103 remains an upper bound for it.
Thus, our task is to understand formula_104 Nevertheless, since trace and expectation are both linear, we can commute them, so it is sufficient to consider formula_105, which we call the matrix generating function. This is where the methods of and diverge. The immediately following presentation follows .
The Golden–Thompson inequality implies that 
Suppose formula_107. We can find an upper bound for formula_108 by iterating this result. Noting that formula_109, then
Iterating this, we get
So far we have found a bound with an infimum over formula_102. In turn, this can be bounded. At any rate, one can see how the Ahlswede–Winter bound arises as the sum of largest eigenvalues.
Tropp.
The major contribution of is the application of Lieb's theorem where had applied the Golden–Thompson inequality. Tropp's corollary is the following: If formula_113 is a fixed self-adjoint matrix and formula_114 is a random self-adjoint matrix, then
Proof: Let formula_116. Then Lieb's theorem tells us that
is concave.
The final step is to use Jensen's inequality to move the expectation inside the function:
This gives us the major result of the paper: the subadditivity of the log of the matrix generating function.
Subadditivity of log mgf.
Let formula_119 be a finite sequence of independent, random self-adjoint matrices. Then for all formula_120,
Proof: It is sufficient to let formula_122. Expanding the definitions, we need to show that 
To complete the proof, we use the law of total expectation. Let formula_124 be the expectation conditioned on formula_125. Since we assume all the formula_126 are independent, 
Define formula_128.
Finally, we have
where at every step m we use Tropp's corollary with 
Master tail bound.
The following is immediate from the previous result:
All of the theorems given above are derived from this bound; the theorems consist in various ways to bound the infimum. These steps are significantly simpler than the proofs given.