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

Suppose I'm trying to estimate the spectral radius of a square $n \times n$ matrix $A$, and let $N$ be a distribution over Gaussian i.i.d. vectors of length $n$.

Is the following lemma true: If the spectral radius of $A$ is larger than $\epsilon$ then with probability at least $1/poly(n)$, a vector $v$ sampled according to $N$ will have $\frac{|v^T A v|}{\left\|v\right\|^2}>\epsilon$.

share|improve this question
    
You mean $\frac{|v^TAv|}{\|v\|^2}$ of course. –  Robert Israel Feb 21 '12 at 18:51
    
Also, either these are complex vectors (and you want the conjugate transpose rather than the transpose) or $A$ is assumed to be a real symmetric matrix. –  Robert Israel Feb 21 '12 at 18:58
    
Also, you'll have to ask not just for "larger than $\epsilon$" but larger than some $\eta > \epsilon$, where the lower bound on probability will have to depend on $\eta/\epsilon$ (and go to $0$ as $\eta/\epsilon \to 1+$). –  Robert Israel Feb 21 '12 at 19:12

1 Answer 1

up vote 5 down vote accepted

No: given $\eta > \epsilon > 0$, there are $n \times n$ symmetric matrices $A_n$ with spectral radius $> \eta$, such that $Pr\left[|v^TA_nv|/\|v\|^2 > \epsilon\right] < e^{-cn}$ for some $c > 0$.

I assume a standard Gaussian distribution, with mean $0$ and covariance matrix $I$. Consider an $n \times n$ diagonal matrix $A$ with one diagonal element $\alpha$ and the other diagonal elements $-\epsilon$, where $\alpha > \eta > \epsilon > 0$. Then $v^T A v = \alpha v_1^2 - \epsilon \sum_{j=2}^{n} v_j^2$, and it is impossible to have $v^T A v < -\eta \|v\|^2$, while $$\eqalign{Pr\left[v^T A v > \eta \|v\|^2 \right] &= Pr\left[ (\alpha - \eta) v_1^2 - \sum_{j=2}^n (\epsilon + \eta) v_j^2 > 0 \right]\cr &\le Pr \left[ (\alpha - \eta) v_1^2 > k (n-1)\right] + Pr\left[ S_n < k (n-1)\right]\cr}$$ for any $0 < k < \epsilon + \eta$, where $S_n = \sum_{j=2}^n (\epsilon + \eta) v_j^2$.

Now $Pr[(\alpha - \eta) v_1^2 > k (n-1)]$ goes to 0 exponentially as $n \to \infty$. On the other hand, $S_n$ has mean $(n-1)(\epsilon+\eta)$, and for any $k < \epsilon + \eta$, $Pr[S_n < k (n-1)]$ goes to $0$ exponentially by the theory of large deviations.

share|improve this answer
    
Thank you for the detailed answer. –  Lior Eldar Feb 21 '12 at 21:15

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.