0
$\begingroup$

When bounding the convergence rate of many numerical linear algebra algorithms (e.g. the Lanczos method), typically one must use a bound on the coefficients of the initial vector in the eigenbasis of the input matrix. I wonder how to prove such a general bound for a uniformly randomly drawn vector from the unit sphere.

My idea so far is the following and I am wondering whether it makes sense: Given a vector $v \in \mathbb{R}^n$ which is drawn random at uniform from the unit sphere, and some orthonormal basis $\{u_1,\ldots,u_n\}$, I decompose this unit vector in this basis, i.e., $v = \sum_i \alpha_i u_i$. The question is now, whether I can lower bound the magnitude of these coefficients in probability, say with $p \geq 1/2$, $\alpha_i \geq \xi$.

My approach is the following very simple one: Let $x$ be the vector with entries $\alpha_i$;

  1. It is straight forward to bound, based on Gaussian concentration bounds the magnitude of the norm of $v$ in high probability.
  2. I could then conditionally on the norm being bounded find a lower bound on the entires, which are $\chi^2$-distributed. However, I was not able to show a lower bound, since in particular I believe that the mean is $0$, which seems to imply that I can only obtain results of the form $\mathbb P(\min_i X_i > t) \leq \sum_{i=1}^n \mathbb P(X_i > t) \leq n \cdot \exp(-t^2/2 \sigma^2)$ and then using that $\min_{1 \leq i \leq n} |X_i| = \min_{1 \leq i \leq 2n} X_i$ for $X_{i+n} = - X_i$ and hence obtaining: $$\mathbb P(\min_i |X_i| > t) \leq 2n \cdot exp(-t^2/2 \sigma^2).$$ However I would need in step three a different bound which lower bounds the probability.
  3. If point (2) can be obtained, then I could just obtain the final success probability in terms of the error rates of the step (1,2) by bounding $\mathbb{P}[v_i/||v|| \geq c/\sqrt{n}] \geq 1 - \delta_1 - \delta_2$, where $\delta_{1/2}$ are the results from the first two steps.

I was wondering if this approach is correct or if there is a better way? Furthermore does anyone have a hint where I can find a lower bound on the minimum of a sub-gaussian distributed variable?

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.