Self-adjoint matrices case

Consider a finite sequence ${\displaystyle \{\mathbf {A} _{k}\}}$ of fixed, self-adjoint matrices with dimension ${\displaystyle d}$, and let ${\displaystyle \{\xi _{k}\}}$ be a finite sequence of independent standard normal or independent Rademacher random variables.

Then, for all ${\displaystyle t\geq 0}$,

${\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

${\displaystyle \sigma ^{2}={\bigg \Vert }\sum _{k}\mathbf {A} _{k}^{2}{\bigg \Vert }.}$

Rectangular case

Consider a finite sequence ${\displaystyle \{\mathbf {B} _{k}\}}$ of fixed, self-adjoint matrices with dimension ${\displaystyle d_{1}\times d_{2}}$, and let ${\displaystyle \{\xi _{k}\}}$ be a finite sequence of independent standard normal or independent Rademacher random variables. Define the variance parameter

${\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 ${\displaystyle t\geq 0}$,

${\displaystyle \Pr \left\{{\bigg \Vert }\sum _{k}\xi _{k}\mathbf {B} _{k}{\bigg \Vert }\geq t\right\}\leq (d_{1}+d_{2})\cdot e^{-t^{2}/2\sigma ^{2}}.}$

Matrix Chernoff I

Consider a finite sequence ${\displaystyle \{\mathbf {X} _{k}\}}$ of independent, random, self-adjoint matrices with dimension ${\displaystyle d}$. Assume that each random matrix satisfies

${\displaystyle \mathbf {X} _{k}\succeq \mathbf {0} \quad {\text{and}}\quad \lambda _{\text{max}}(\mathbf {X} _{k})\leq R}$

almost surely.

Define

${\displaystyle \mu _{\text{min}}=\lambda _{\text{min}}\left(\sum _{k}\mathbb {E} \,\mathbf {X} _{k}\right)\quad {\text{and}}\quad \mu _{\text{max}}=\lambda _{\text{max}}\left(\sum _{k}\mathbb {E} \,\mathbf {X} _{k}\right).}$

Then

${\displaystyle \Pr \left\{\lambda _{\text{min}}\left(\sum _{k}\mathbf {X} _{k}\right)\leq (1-\delta )\mu _{\text{min}}\right\}\leq d\cdot \left[{\frac {e^{-\delta }}{(1-\delta )^{1-\delta }}}\right]^{\mu _{\text{min}}/R}\quad {\text{for }}\delta \in [0,1){\text{, and}}}$

${\displaystyle \Pr \left\{\lambda _{\text{max}}\left(\sum _{k}\mathbf {X} _{k}\right)\geq (1+\delta )\mu _{\text{max}}\right\}\leq d\cdot \left[{\frac {e^{\delta }}{(1+\delta )^{1+\delta }}}\right]^{\mu _{\text{max}}/R}\quad {\text{for }}\delta \geq 0.}$

Matrix Chernoff II

Consider a sequence ${\displaystyle \{\mathbf {X} _{k}:k=1,2,\ldots ,n\}}$ of independent, random, self-adjoint matrices that satisfy

${\displaystyle \mathbf {X} _{k}\succeq \mathbf {0} \quad {\text{and}}\quad \lambda _{\text{max}}(\mathbf {X} _{k})\leq 1}$

almost surely.

Compute the minimum and maximum eigenvalues of the average expectation,

${\displaystyle {\bar {\mu }}_{\text{min}}=\lambda _{\text{min}}\left({\frac {1}{n}}\sum _{k=1}^{n}\mathbb {E} \,\mathbf {X} _{k}\right)\quad {\text{and}}\quad {\bar {\mu }}_{\text{max}}=\lambda _{\text{max}}\left({\frac {1}{n}}\sum _{k=1}^{n}\mathbb {E} \,\mathbf {X} _{k}\right).}$

Then

${\displaystyle \Pr \left\{\lambda _{\text{min}}\left({\frac {1}{n}}\sum _{k=1}^{n}\mathbf {X} _{k}\right)\leq \alpha \right\}\leq d\cdot e^{-nD(\alpha \Vert {\bar {\mu }}_{\text{min}})}\quad {\text{for }}0\leq \alpha \leq {\bar {\mu }}_{\text{min}}{\text{, and}}}$

${\displaystyle \Pr \left\{\lambda _{\text{max}}\left({\frac {1}{n}}\sum _{k=1}^{n}\mathbf {X} _{k}\right)\geq \alpha \right\}\leq d\cdot e^{-nD(\alpha \Vert {\bar {\mu }}_{\text{max}})}\quad {\text{for }}{\bar {\mu }}_{\text{max}}\leq \alpha \leq 1.}$

The binary information divergence is defined as

${\displaystyle D(a\Vert u)=a\left(\log a-\log u\right)+(1-a)\left(\log(1-a)-\log(1-u)\right)}$

for ${\displaystyle a,u\in [0,1]}$.

Bounded case

Consider a finite sequence ${\displaystyle \{\mathbf {X} _{k}\}}$ of independent, random, self-adjoint matrices with dimension ${\displaystyle d}$. Assume that each random matrix satisfies

${\displaystyle \mathbb {E} \mathbf {X} _{k}=\mathbf {0} \quad {\text{and}}\quad \lambda _{\text{max}}(\mathbf {X} _{k})\leq R}$

almost surely.

Compute the norm of the total variance,

${\displaystyle \sigma ^{2}={\bigg \Vert }\sum _{k}\mathbb {E} \,(\mathbf {X} _{k}^{2}){\bigg \Vert }.}$

Then, the following chain of inequalities holds for all ${\displaystyle t\geq 0}$:

${\displaystyle {\begin{aligned}\Pr \left\{\lambda _{\text{max}}\left(\sum _{k}\mathbf {X} _{k}\right)\geq t\right\}&\leq d\cdot \exp \left(-{\frac {\sigma ^{2}}{R^{2}}}\cdot h\left({\frac {Rt}{\sigma ^{2}}}\right)\right)\\&\leq d\cdot \exp \left({\frac {-t^{2}}{\sigma ^{2}+Rt/3}}\right)\\&\leq {\begin{cases}d\cdot \exp(-3t^{2}/8\sigma ^{2})\quad &{\text{for }}t\leq \sigma ^{2}/R;\\d\cdot \exp(-3t/8R)\quad &{\text{for }}t\geq \sigma ^{2}/R.\\\end{cases}}\end{aligned}}}$

The function ${\displaystyle h(u)}$ is defined as ${\displaystyle h(u)=(1+u)\log(1+u)-u}$ for ${\displaystyle u\geq 0}$.

Subexponential case

Consider a finite sequence ${\displaystyle \{\mathbf {X} _{k}\}}$ of independent, random, self-adjoint matrices with dimension ${\displaystyle d}$. Assume that

${\displaystyle \mathbb {E} \,\mathbf {X} _{k}=\mathbf {0} \quad {\text{and}}\quad \mathbb {E} \,(\mathbf {X} _{k}^{p})\preceq {\frac {p!}{2}}\cdot R^{p-2}\mathbf {A} _{k}^{2}}$

for ${\displaystyle p=2,3,4,\ldots }$.

Compute the variance parameter,

${\displaystyle \sigma ^{2}={\bigg \Vert }\sum _{k}\mathbf {A} _{k}^{2}{\bigg \Vert }.}$

Then, the following chain of inequalities holds for all ${\displaystyle t\geq 0}$:

${\displaystyle {\begin{aligned}\Pr \left\{\lambda _{\text{max}}\left(\sum _{k}\mathbf {X} _{k}\right)\geq t\right\}&\leq d\cdot \exp \left({\frac {-t^{2}/2}{\sigma ^{2}+Rt}}\right)\\&\leq {\begin{cases}d\cdot \exp(-t^{2}/4\sigma ^{2})\quad &{\text{for }}t\leq \sigma ^{2}/R;\\d\cdot \exp(-t/4R)\quad &{\text{for }}t\geq \sigma ^{2}/R.\\\end{cases}}\end{aligned}}}$

Rectangular case

Consider a finite sequence ${\displaystyle \{\mathbf {Z} _{k}\}}$ of independent, random, matrices with dimension ${\displaystyle d_{1}\times d_{2}}$. Assume that each random matrix satisfies

${\displaystyle \mathbb {E} \,\mathbf {Z} _{k}=\mathbf {0} \quad {\text{and}}\quad \Vert \mathbf {Z} _{k}\Vert \leq R}$

almost surely. Define the variance parameter

${\displaystyle \sigma ^{2}=\max \left\{{\bigg \Vert }\sum _{k}\mathbb {E} \,(\mathbf {Z} _{k}\mathbf {Z} _{k}^{*}){\bigg \Vert },{\bigg \Vert }\sum _{k}\mathbb {E} \,(\mathbf {Z} _{k}^{*}\mathbf {Z} _{k}){\bigg \Vert }\right\}.}$

Then, for all ${\displaystyle t\geq 0}$

${\displaystyle \Pr \left\{{\bigg \Vert }\sum _{k}\mathbf {Z} _{k}{\bigg \Vert }\geq t\right\}\leq (d_{1}+d_{2})\cdot \exp \left({\frac {-t^{2}/2}{\sigma ^{2}+Rt/3}}\right)}$

holds.^[1]

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 ${\displaystyle \{\mathbf {X} _{k}\}}$ of self-adjoint matrices with dimension ${\displaystyle d}$, and a fixed sequence ${\displaystyle \{\mathbf {A} _{k}\}}$ of self-adjoint matrices that satisfy

${\displaystyle \mathbb {E} _{k-1}\,\mathbf {X} _{k}=\mathbf {0} \quad {\text{and}}\quad \mathbf {X} _{k}^{2}\preceq \mathbf {A} _{k}^{2}}$

almost surely.

Compute the variance parameter

${\displaystyle \sigma ^{2}={\bigg \Vert }\sum _{k}\mathbf {A} _{k}^{2}{\bigg \Vert }.}$

Then, for all ${\displaystyle t\geq 0}$

${\displaystyle \Pr \left\{\lambda _{\text{max}}\left(\sum _{k}\mathbf {X} _{k}\right)\geq t\right\}\leq d\cdot e^{-t^{2}/8\sigma ^{2}}}$

The constant 1/8 can be improved to 1/2 when there is additional information available. One case occurs when each summand ${\displaystyle \mathbf {X} _{k}}$ is conditionally symmetric. Another example requires the assumption that ${\displaystyle \mathbf {X} _{k}}$ commutes almost surely with ${\displaystyle \mathbf {A} _{k}}$.

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 ${\displaystyle \{\mathbf {X} _{k}\}}$ of independent, random, self-adjoint matrices with dimension ${\displaystyle d}$, and let ${\displaystyle \{\mathbf {A} _{k}\}}$ be a sequence of fixed self-adjoint matrices. Assume that each random matrix satisfies

${\displaystyle \mathbb {E} \,\mathbf {X} _{k}=\mathbf {0} \quad {\text{and}}\quad \mathbf {X} _{k}^{2}\preceq \mathbf {A} _{k}^{2}}$

almost surely.

Then, for all ${\displaystyle t\geq 0}$

${\displaystyle \Pr \left\{\lambda _{\text{max}}\left(\sum _{k}\mathbf {X} _{k}\right)\geq t\right\}\leq d\cdot e^{-t^{2}/8\sigma ^{2}}}$

where

${\displaystyle \sigma ^{2}={\bigg \Vert }\sum _{k}\mathbf {A} _{k}^{2}{\bigg \Vert }.}$

An improvement of this result was established in (Mackey et al. 2012): for all ${\displaystyle t\geq 0}$

${\displaystyle \Pr \left\{\lambda _{\text{max}}\left(\sum _{k}\mathbf {X} _{k}\right)\geq t\right\}\leq d\cdot e^{-t^{2}/2\sigma ^{2}}}$

where

${\displaystyle \sigma ^{2}={\frac {1}{2}}{\bigg \Vert }\sum _{k}\mathbf {A} _{k}^{2}+\mathbb {E} \,\mathbf {X} _{k}^{2}{\bigg \Vert }\leq {\bigg \Vert }\sum _{k}\mathbf {A} _{k}^{2}{\bigg \Vert }.}$

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 ${\displaystyle \{Z_{k}:k=1,2,\ldots ,n\}}$ be an independent, family of random variables, and let ${\displaystyle \mathbf {H} }$ be a function that maps ${\displaystyle n}$ variables to a self-adjoint matrix of dimension ${\displaystyle d}$. Consider a sequence ${\displaystyle \{\mathbf {A} _{k}\}}$ of fixed self-adjoint matrices that satisfy

${\displaystyle \left(\mathbf {H} (z_{1},\ldots ,z_{k},\ldots ,z_{n})-\mathbf {H} (z_{1},\ldots ,z'_{k},\ldots ,z_{n})\right)^{2}\preceq \mathbf {A} _{k}^{2},}$

where ${\displaystyle z_{i}}$ and ${\displaystyle z'_{i}}$ range over all possible values of ${\displaystyle Z_{i}}$ for each index ${\displaystyle i}$. Compute the variance parameter

${\displaystyle \sigma ^{2}={\bigg \Vert }\sum _{k}\mathbf {A} _{k}^{2}{\bigg \Vert }.}$

Then, for all ${\displaystyle t\geq 0}$

${\displaystyle \Pr \left\{\lambda _{\text{max}}\left(\mathbf {H} (\mathbf {z} )-\mathbb {E} \,\mathbf {H} (\mathbf {z} )\right)\geq t\right\}\leq d\cdot e^{-t^{2}/8\sigma ^{2}},}$

where ${\displaystyle \mathbf {z} =(Z_{1},\ldots ,Z_{n})}$.

An improvement of this result was established in (Paulin, Mackey & Tropp 2013) (see also (Paulin, Mackey & Tropp 2016)): for all ${\displaystyle t\geq 0}$

${\displaystyle \Pr \left\{\lambda _{\text{max}}\left(\mathbf {H} (\mathbf {z} )-\mathbb {E} \,\mathbf {H} (\mathbf {z} )\right)\geq t\right\}\leq d\cdot e^{-t^{2}/\sigma ^{2}},}$

where ${\displaystyle \mathbf {z} =(Z_{1},\ldots ,Z_{n})}$ and ${\displaystyle \sigma ^{2}={\bigg \Vert }\sum _{k}\mathbf {A} _{k}^{2}{\bigg \Vert }.}$

Ahlswede and Winter

The Laplace transform argument found in (Ahlswede & Winter 2003) is a significant result in its own right: Let ${\displaystyle \mathbf {Y} }$ be a random self-adjoint matrix. Then

${\displaystyle \Pr \left\{\lambda _{\max }(Y)\geq t\right\}\leq \inf _{\theta >0}\left\{e^{-\theta t}\cdot \operatorname {E} \left[\operatorname {tr} e^{\theta \mathbf {Y} }\right]\right\}.}$

To prove this, fix ${\displaystyle \theta >0}$. Then

${\displaystyle {\begin{aligned}\Pr \left\{\lambda _{\max }(\mathbf {Y} )\geq t\right\}&=\Pr \left\{\lambda _{\max }(\mathbf {\theta Y} )\geq \theta t\right\}\\&=\Pr \left\{e^{\lambda _{\max }(\theta \mathbf {Y} )}\geq e^{\theta t}\right\}\\&\leq e^{-\theta t}\operatorname {E} e^{\lambda _{\max }(\theta \mathbf {Y} )}\\&\leq e^{-\theta t}\operatorname {E} \operatorname {tr} e^{(\theta \mathbf {Y} )}\end{aligned}}}$

The second-to-last inequality is Markov's inequality. The last inequality holds since ${\displaystyle e^{\lambda _{\max }(\theta \mathbf {Y} )}=\lambda _{\max }(e^{\theta \mathbf {Y} })\leq \operatorname {tr} (e^{\theta \mathbf {Y} })}$. Since the left-most quantity is independent of ${\displaystyle \theta }$, the infimum over ${\displaystyle \theta >0}$ remains an upper bound for it.

Thus, our task is to understand ${\displaystyle \operatorname {E} [\operatorname {tr} (e^{\theta \mathbf {Y} })]}$ Nevertheless, since trace and expectation are both linear, we can commute them, so it is sufficient to consider ${\displaystyle \operatorname {E} e^{\theta \mathbf {Y} }:=\mathbf {M} _{\mathbf {Y} }(\theta )}$, which we call the matrix generating function. This is where the methods of (Ahlswede & Winter 2003) and (Tropp 2010) diverge. The immediately following presentation follows (Ahlswede & Winter 2003).

The Golden–Thompson inequality implies that

${\displaystyle \operatorname {tr} \mathbf {M} _{\mathbf {X} _{1}+\mathbf {X} _{2}}(\theta )\leq \operatorname {tr} \left[\left(\operatorname {E} e^{\theta \mathbf {X} _{1}}\right)\left(\operatorname {E} e^{\theta \mathbf {X} _{2}}\right)\right]=\operatorname {tr} \mathbf {M} _{\mathbf {X} _{1}}(\theta )\mathbf {M} _{\mathbf {X} _{2}}(\theta )}$, where we used the linearity of expectation several times.

Suppose ${\displaystyle \mathbf {Y} =\sum _{k}\mathbf {X} _{k}}$. We can find an upper bound for ${\displaystyle \operatorname {tr} \mathbf {M} _{\mathbf {Y} }(\theta )}$ by iterating this result. Noting that ${\displaystyle \operatorname {tr} (\mathbf {AB} )\leq \operatorname {tr} (\mathbf {A} )\lambda _{\max }(\mathbf {B} )}$, then

${\displaystyle \operatorname {tr} \mathbf {M} _{\mathbf {Y} }(\theta )\leq \operatorname {tr} \left[\left(\operatorname {E} e^{\sum _{k=1}^{n-1}\theta \mathbf {X} _{k}}\right)\left(\operatorname {E} e^{\theta \mathbf {X} _{n}}\right)\right]\leq \operatorname {tr} \left(\operatorname {E} e^{\sum _{k=1}^{n-1}\theta \mathbf {X} _{k}}\right)\lambda _{\max }(\operatorname {E} e^{\theta \mathbf {X} _{n}}).}$

Iterating this, we get

${\displaystyle \operatorname {tr} \mathbf {M} _{\mathbf {Y} }(\theta )\leq (\operatorname {tr} \mathbf {I} )\left[\Pi _{k}\lambda _{\max }(\operatorname {E} e^{\theta \mathbf {X} _{k}})\right]=de^{\sum _{k}\lambda _{\max }\left(\log \operatorname {E} e^{\theta \mathbf {X} _{k}}\right)}}$

So far we have found a bound with an infimum over ${\displaystyle \theta }$. 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 (Tropp 2010) is the application of Lieb's theorem where (Ahlswede & Winter 2003) had applied the Golden–Thompson inequality. Tropp's corollary is the following: If ${\displaystyle H}$ is a fixed self-adjoint matrix and ${\displaystyle X}$ is a random self-adjoint matrix, then

${\displaystyle \operatorname {E} \operatorname {tr} e^{\mathbf {H} +\mathbf {X} }\leq \operatorname {tr} e^{\mathbf {H} +\log(\operatorname {E} e^{\mathbf {X} })}}$

Proof: Let ${\displaystyle \mathbf {Y} =e^{\mathbf {X} }}$. Then Lieb's theorem tells us that

${\displaystyle f(\mathbf {Y} )=\operatorname {tr} e^{\mathbf {H} +\log(\mathbf {Y} )}}$

is concave. The final step is to use Jensen's inequality to move the expectation inside the function:

${\displaystyle \operatorname {E} \operatorname {tr} e^{\mathbf {H} +\log(\mathbf {Y} )}\leq \operatorname {tr} e^{\mathbf {H} +\log(\operatorname {E} \mathbf {Y} )}.}$

This gives us the major result of the paper: the subadditivity of the log of the matrix generating function.