Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Typical results from the literature of Random Matrix Theory (RMT) (e.g., Tropp'11, Vershynin'12) provide probabilistic guarantees for large deviation of the extreme eigenvalues of random matrices like $\lambda_{\max}\left(\overline{X}:=\sum_{i=1}^m X_i\right) \leq \mathbb{E}\left[\sum_{i=1}^m\lambda_{\max}\left(X_i\right)\right]+ m\epsilon$, where $X_i$'s are $d\times d$ random matrices and $\epsilon$ is small positive constant. One of the common assumptions made in these analyses to establish the desired guarantees is that the random matrices are bounded from above with respect to the spectral norm or the largest eigenvalue almost surely. In some simple scenarios this assumption the confidence on the eigenvalue bounds is suboptimal compared to results obtained using different techniques.

To be concrete let's consider a simple example. Suppose that $X_i = x_i x_i^\mathrm{T}$ where $x_i$'s are iid Rademacher vectors (i.e., the entries of $x_i$ are iid uniformly distributed $+1$ and $-1$). Note that satisfy the condition $\lambda_{\max}\left(X_i\right)\leq d$ almost surely. Applying the RMT results (i.e, matrix versions of the Chernoff, Bernstein, etc inequalities) generally provide bounds on deviation of $\lambda_{\max}\left(\overline{X}\right)$ (and $\lambda_{\min}\left(\overline{X}\right)$) that will fail with probability at most $\exp\left(-c_1\left(\epsilon\right)m/d\right)$ with $c_1\left(\epsilon\right)$ being a positive constant depending only on $\epsilon$ mentioned above. This is worse than the results that do not use the RMT and yield failure probabilities on the order of $\exp\left(-c_2\left(\epsilon\right)m\right)$.

So my questions are:

  1. Is there something fundamental to the RMT analyses that yield these suboptimal results? Under what conditions we can get sharper confidence probabilities like the example above?
  2. (on a slightly different path), assuming that random matrices in the summation are bounded is too restrictive, e.g., it even excludes Gaussian matrices. Is there any relevant result beyond the simple cases that doesn't need the boundedness assumption preferably with the sharper confidence guarantee?
share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.