Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 0 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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