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

  • $\begingroup$ You mean $\frac{|v^TAv|}{\|v\|^2}$ of course. $\endgroup$ – Robert Israel Feb 21 '12 at 18:51
  • $\begingroup$ 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. $\endgroup$ – Robert Israel Feb 21 '12 at 18:58
  • $\begingroup$ 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+$). $\endgroup$ – Robert Israel Feb 21 '12 at 19:12

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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