MathOverflow is a question and answer site for professional mathematicians. 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

Suppose that $X_1,X_2,\ldots,X_m$ are independent $d\times d$ random matrices and let $\overline{X} := \frac{1}{m}\sum_{i=1}^m X_i$. One of the questions studied under the theory of random matrices is that if and at what rate $\lambda_{\max}\bigl(\overline{X}\bigr)$ (i.e., the largest eigenvalue of $\overline{X}$) converges to $\mathbb{E}\left[\lambda_{\max}\bigl(\overline{X}\bigr)\right]$ as $m\to +\infty$.

To obtain such guarantees, some assumptions are usually made about the $X_i$'s. For instance, it may be assumed that $X_i$'s are self-adjoint, have independent sub-gaussian or sub-exponential entries, etc. As far as I've read the literature, there's one particular assumption---namely $\lambda_{\max}\bigl(X_i\bigr)\leq R$ almost surely---that is made in almost every studied case. For instance, using this boundedness assumption, the matrix versions of the Chernoff's and Bernstein's inequalities as well as some other inequalities (see e.g., Vershynin'12, Tropp'11, MacKey et al'12, Hsu et al'12) can guarantee concentration inequalities of the form $$\Pr\left\{ \left|\lambda_{\max}\bigl(\overline{X}\bigr)-\mathbb{E}\left[\lambda_{\max}\bigl(\overline{X}\bigr)\right]\right|\geq \epsilon \right\} \leq d\exp\left(-\epsilon^2m/R\right).$$ They may vary in the exponent of $\epsilon$, the coefficient of the exponential, or the denominator inside the $\exp\left(\cdot\right)$, but they all decay at a rate in the order $m/R$.

Now, here's the issue. Suppose that $X_i=x_ix_i^\mathrm{T}$ where the $x_i$'s are iid vectors whose entries are iid Rademacher random variables. Then we get $\lambda_{\max}\left(X_i\right)=d$, so the best $R$ we can choose is $d$. Thus the probability bound expressed above decays at a rate not faster than $m/d$. The same rate holds if instead of Rademacher we use uniformly distributed zero-mean random variables. However, it is known, e.g. from Compressed Sensing literature, for these examples that the above probability bound for $\overline{X}$ decays at least at a rate of $m$ independent of $d$.

My question is why the bounds obtained in random matrix theory literature do not yield the sharpest convergence rates for these simple cases? Is this a by-product of the employed techniques or is there something fundamental that prevents it ?

Furthermore, is there any way to get rid of the assumption $\lambda_{\max}\left(X_i\right)\leq R$ a.s., altogether? This seems to be too restrictive, e.g., it doesn't even permit Gaussian random variables. It might be possible to resolve this issue using the relaxed versions of the concentration inequalities such as e.g. the extension of McDiarmid's inequality proposed by Kutin'02, but I think the first caveat still persists.

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.