0

I am using the Bernstein inequality for the sum of independent random Hermitian matrices presented in the following paper by Joel A.Tropp (page 96, theorem 6.6.1) which states the following:

Consider a finite sequence $\{X_k\}$ of independent, random, Hermitian matrices with dimension $d$.

Assume that $E(X_k) =0$ and $ \lambda_{max}(X_k) \leq L$ for each index $k$. Introduce the random matrix $Y =\sum_{k} X_k$.

Let $v (Y)$ be the matrix variance statistic of the sum: $v(Y)= \|EY^2\| = \|\sum_{k} EX^{2}_{k}\|$

Then for all $t \geq 0$

$$P\{\lambda_{max}(Y) \geq t\} \leq d·\exp \left(\frac{−t^2/2}{v(Y)+Lt/3}\right).$$

For the problem I am working on, the sequence of random matrices $\{X_k\}$ are also diagonal matrices, I am therefore wondering if that information can be used to improve the bound of the inequality.

Also what if each of the matrices where not only diagonal but also only had one non-zero diagonal element?

In other word what if the matrix $X_k$ has a value on the $kk$ diagonal position and zeros everywhere else for all $k \in \{1,..,d\}$.

Thank you

Imelda Lacroix
  • 1
  • I doubt there’s much improvement. The reason is the diagonal case is the same as considering the maximum of scalar random variables, and you’ll basically pay a union bound, which is the $d$ multiplicative factor. – J.G Jun 20 '20 at 02:39
  • Thank you very much for your answer. Indeed my first attempt at solving the problem was to rely on the fact that the largest element (in absolute value) on the diagonal is the spectral norm but then I thought that maybe I could improve the bound by reformulating the problem as a sum of diagonal matrices. Does that mean that whether a matrix is sparse or dense has no bearing on its concentration bound ? – Imelda Lacroix Jun 20 '20 at 04:13

0 Answers0