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



Estimating spectral radius with a Gaussian vector
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. 


