1
$\begingroup$

Let $[X_1, X_2, ..., X_r]$ be a set of independent $d_1 \times d_2$ dimensional random matrices with $\mathbb{E}(X_i) = 0$ and $\|X_i\| \leq B$ (bounded operator norm).

Introduce the sum of random matrices, $Z = \sum_{i=1}^r X_i$

Define matrix variance proxy:

$$\sigma^2 = \max \left( \| \mathbb{E}(ZZ^T)\|, \|\mathbb{E}(Z^TZ) \|\right) .$$

Then Bernstein inequality for rectangular matrices states that:

$$P(\|Z\| \geq t) \leq (d_1+d_2)\exp\left(\frac{-t^2/2}{\sigma^2 + Bt/3}\right).$$

However, I have also seen people use the following version:

$$P(\|Z\| \geq t) \leq 2(d_1+d_2)\exp\left(\frac{-t^2/2}{\sigma^2 + Bt}\right).$$

My question is how these two inequalities are related to each other? Does one imply another or they are equivalent?

$\endgroup$
1
$\begingroup$

Isn't the first inequality just strictly stronger than the second? As \begin{equation} \sigma^2+Bt/3<\sigma^2+Bt\implies \exp\left(\frac{-t^2/2}{\sigma^2+Bt/3}\right)<\exp\left(\frac{-t^2/2}{\sigma^2+Bt}\right), \end{equation} and obviously the $2$ factor only makes the second inequality worse.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.