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