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?


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.