matrix martingale inequalities

Variance bound

Matrix version of Variance bound. Suppose $X_1,\dots ,X_n$ is a matrix-valued martingale of Hermitian Matrices adapted to some filtration $\mathcal{F}$, i.e., $\mathbb{E}[X_i|{\mathcal{F}}_{i-1}]=X_{i-1}$. Let $D_i=X_i-X_{i-1}$ and suppose

$$\left|D_i\right|\le c_i,\left|\mathbb{E}[D_i^2|{\mathcal{F}}_{i-1}]\right|\le {\sigma }_i^2.$$

Then, for $V_n={\sum }_{i\le n}{\sigma }_i^2$,

$$\mathbb{P}(\left|X_n\right|>ϵ)\le 2d\exp \left(\frac{-{ϵ}^2}{4V_n}\right),$$

where each $X_t$ is a $(d\times d)$-matrix. This was first proved by David Gross: Recovering Low-Rank Matrices From Few Coefficients In Any Basis.

Bennett-style bound

Let $X_1,X_2,\dots$ be a matrix valued martingale difference sequence ($\mathbb{E}[X_i|{\mathcal{F}}_{i-1}]=0$) adapted to $\mathcal{F}$ with ${\lambda }_{\max }(X_i)\le K$ for all $i$. Let $S_k={\sum }_{i\le k}{X}_i$ and ${\Sigma }_k={\sum }_{i\le k}\mathbb{E}[X_i^2|{\mathcal{F}}_{i-1}{]}^2$. Then,

$$\mathbb{P}\left(\exists t\ge 0:{\lambda }_{\max }(S_t)\ge u\text{ and }\Vert {\Sigma }_t\Vert \le {\sigma }^2\right)\le d\exp \left\{-\frac{{\sigma }^2}{K^2}h\left(\frac{Ku}{{\sigma }^2}\right)\right\},$$

where $h$ is as in Bennett’s inequality. This was proved by Tropp in 2011, Theorem 3.1. This a Freedman-style inequality.