I am looking for the tail bound of spectral norm for certain type of random matrix.


Let's say we have a $n\times n$ symmetric random matrix $R$, and for each entry $R\_{ij}$, we have that 
$$
E[R\_{ij}]=0
$$
$$
Var[R\_{ij}]\leq C
$$
$$
|Cov[R\_{ij},R\_{lm}]|\leq C/n,\quad if\quad (ij\neq lm) \cup (ij\neq ml) 
$$


And I need a tail bound on the spectral norm of $R$.


Our current approach does not utilize the bound on $|Cov[R\_{ij},R\_{lm}]|$. Our approach is as follows,




---


By Gershgorin circle theorem, we have that 
$$
||R||\_2 \leq \max\_i \sum\_{j=1}^n |R\_{ij}|
$$


Assume that $Var[R\_{ij}]\leq C,\forall i,j$, we also have the following


$$
E[R\_{ij}]=0
$$


$$
Var[|R\_{ij}|]=E[|R\_{ij}|^2]-E^2[|R\_{ij}|]=Var[R\_{ij}]-E^2[|R\_{ij}|] \leq Var[R\_{ij}]
$$
and 
$$
C \geq Var[R\_{ij}]\geq E^2[|R\_{ij}|]
$$


So we have


$$
E[\sum\_{j=1}^n |R\_{ij}|] =\sum\_{j=1}^n E[ |R\_{ij}|] \leq n\sqrt{C}
$$
and 
$$
Var[\sum\_{j=1}^n |R\_{ij}|] \leq n^2 Var[R\_{ij}] \leq n^2 C
$$


By Chebyshev's inequality, we have 
$$
{Pr}(\sum\_{j=1}^n |R\_{ij}| \geq n\sqrt{C} + k n\sqrt{C} ) \leq \frac{1}{k^2}
$$


And by union bound, we have that
$$
{Pr}(\max\_i \sum\_{j=1}^n |R\_{ij}| \geq n\sqrt{C} + k n\sqrt{C} ) \leq n\frac{1}{k^2}
$$
By setting $k = \sqrt{\frac{n}{\delta }}$, we have that with probability $1-\delta$
$$
||R||\_2 \leq \max\_i \sum\_{j=1}^n |R\_{ij}| \leq (1+ \sqrt{\frac{n}{\delta }} ) n\sqrt{C}
$$




---


**Our goal is to remove the extra $\sqrt{n}$ in the coefficient**


In our approach, we obtained the tail bound on $\sum\_{j=1}^n |R\_{ij}|$ by assuming that they are fully correlated (corr=1). 


**If we can prove that $|Cov(|R\_{ij}|,|R\_{ik}|)|\leq \theta C/n$ for some constant $\theta$, we can remove the extra $\sqrt{n}$ directly. But we don't know how to prove it or whether it's true or not.**


Or is there are better way to obtain the tail bound? Is there any result in random matrices literature that can be applied to this type of problem? 



Spectral norm tail bound of a correlated random matrix
I am now answering my own question. I realize that I can bound the Spectral norm by the Frobenius norm. 


The square of Frobenius norm is
$$
||R||\_F^2 = \sum\_{i,j} R\_{ij}^2
$$


So
$$
E[||R||\_F^2] = \sum\_{i,j} Var[R\_{ij}] \leq n^2 C
$$


By Markov inequality, we have


$$
Pr(||R||\_F^2 \geq kn^2 C) \leq 1/k
$$


So 


$$
Pr(||R||\_F \geq n \sqrt{kC}) \leq 1/k
$$


By setting $k=1/\delta$, we have


$$
Pr(||R||\_2 \geq \frac{n}{\sqrt{\delta}} \sqrt{C}) \leq Pr(||R||\_F \geq \frac{n}{\sqrt{\delta}} \sqrt{C}) \leq \delta
$$


