operator norm inequalities

A summary of bounds on the operator norm of random operators. See also matrix martingale inequalities, but I’m also linking these below because I’m a bit confused about how to organize matrix bounds if we’re being honest.

Variance bound

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.

Link to original

Bennet-style bound

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.

Link to original

Bernstein-style bound

This replaces boundedness of the maximum eigenvalue with a moment condition. Let $X_1,\dots ,X_n$ satisfy $\mathbb{E}{X}_i=0$ and $\mathbb{E}{X}_i^p\le \frac{p!}{2}{K}^{p-2}{\Sigma }_i$ (Loewner order). If ${\sigma }^2=\Vert {\sum }_i{\Sigma }_i\Vert$ then

$$\mathbb{P}({\lambda }_{\max }(S_n)\ge u)\le d\exp \left(-\frac{u^2}{2({\sigma }^2+Ku)}\right).$$

This was proved by Tropp in 2012.

Dimension-free Bernstein inequality

This is given by Minsker. If $X_1,\dots ,X_n$ are independent and self-adjoint with $\mathbb{E}{X}_i=0$, $\Vert X_i\Vert \le U$ and ${\sigma }^2\ge \Vert {\sum }_i\mathbb{E}{X}_i^2\Vert$, then

$$\mathbb{P}(\Vert \sum _i{X}_i\Vert >t)\le \frac{2\text{Tr}({\sum }_i\mathbb{E}{X}_i^2)}{{\sigma }^2}\exp (-f(t))g(t),$$

where

$$f(t)=\frac{t^2/2}{{\sigma }^2+t/3},g(t)=1+\frac{6}{t^2{\log }^2(1+t/{\sigma }^2)}.$$

Note that $g(t)$ is decreasing.