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 { X k } {\displaystyle \{\mathbf {X} _{k}\}} 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:
Pr { λ max ( ∑ k X k ) ≥ t } {\displaystyle \Pr \left\{\lambda _{\max }\left(\sum _{k}\mathbf {X} _{k}\right)\geq t\right\}}
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 (Tropp 2010), 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 { A k } {\displaystyle \{\mathbf {A} _{k}\}} of fixed, self-adjoint matrices with dimension d {\displaystyle d} , and let { ξ k } {\displaystyle \{\xi _{k}\}} be a finite sequence of independent standard normal or independent Rademacher random variables. Then, for all t ≥ 0 {\displaystyle t\geq 0} ,
Pr { λ max ( ∑ k ξ k A k ) ≥ t } ≤ d ⋅ e − t 2 / 2 σ 2 {\displaystyle \Pr \left\{\lambda _{\text{max}}\left(\sum _{k}\xi _{k}\mathbf {A} _{k}\right)\geq t\right\}\leq d\cdot e^{-t^{2}/2\sigma ^{2}}}
where
σ 2 = ‖ ∑ k A k 2 ‖ . {\displaystyle \sigma ^{2}={\bigg \Vert }\sum _{k}\mathbf {A} _{k}^{2}{\bigg \Vert }.}
Rectangular case Consider a finite sequence { B k } {\displaystyle \{\mathbf {B} _{k}\}} of fixed matrices with dimension d 1 × d 2 {\displaystyle d_{1}\times d_{2}} , and let { ξ k } {\displaystyle \{\xi _{k}\}} be a finite sequence of independent standard normal or independent Rademacher random variables. Define the variance parameter
σ 2 = max { ‖ ∑ k B k B k ∗ ‖ , ‖ ∑ k B k ∗ B k ‖ } . {\displaystyle \sigma ^{2}=\max \left\{{\bigg \Vert }\sum _{k}\mathbf {B} _{k}\mathbf {B} _{k}^{*}{\bigg \Vert },{\bigg \Vert }\sum _{k}\mathbf {B} _{k}^{*}\mathbf {B} _{k}{\bigg \Vert }\right\}.}
Then, for all t ≥ 0 {\displaystyle t\geq 0} ,
… excerpt ends here. Continue reading the full article.
