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?


1 Answer 1


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 $$


$$ 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 $$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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