How fast can extreme eigenvalues of the average of random matrices converge to their expectation? - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T08:10:52Z http://mathoverflow.net/feeds/question/102185 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/102185/how-fast-can-extreme-eigenvalues-of-the-average-of-random-matrices-converge-to-th How fast can extreme eigenvalues of the average of random matrices converge to their expectation? sbahmani 2012-07-13T21:33:50Z 2012-07-13T22:10:43Z <p>Suppose that $X_1,X_2,\ldots,X_m$ are $m$ 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}\left(\overline{X}\right)$ (i.e., the largest eigenvalue of $\overline{X}$) converges to $\mathbb{E}\left[\lambda_{\max}\left(\overline{X}\right)\right]$ as $m\to +\infty$.</p> <p>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}\left(X_i\right)\leq R$ <em>almost surely</em>---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., <a href="http://www-personal.umich.edu/~romanv/papers/non-asymptotic-rmt-plain.pdf" rel="nofollow">Vershynin'12</a>, <a href="http://users.cms.caltech.edu/~jtropp/papers/Tro11-User-Friendly-FOCM.pdf" rel="nofollow">Tropp'11</a>, <a href="http://users.cms.caltech.edu/~jtropp/papers/MJCFT12-Matrix-Concentration.pdf" rel="nofollow">MacKey et al'12</a>, <a href="http://cseweb.ucsd.edu/~djhsu/papers/randmatrix-ecp.pdf" rel="nofollow">Hsu et al'12</a>) can guarantee concentration inequalities of the form $\Pr\lbrace \left|\lambda_{\max}\left(\overline{X}\right)-\mathbb{E}\left[\lambda_{\max}\left(\overline{X}\right)\right]\right|\geq \epsilon \rbrace \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$.</p> <p>Now, here's the issue. Suppose that $X_i=x_ix_i^\mathrm{T}$ where $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 the above probability bound for $\overline{X}$ decays at least at a rate of $m$ independent and independent of $d$.</p> <p>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 byproduct of the employed techniques or it is something fundamental that prevents ?</p> <p>Furthermore, is there any way to get rid of the assumption $\lambda_{\max}\left(X_i\right)\leq R$ <em>a.s.</em>, 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, extension to McDiarmid's inequality proposed by <a href="http://www.cs.uchicago.edu/files/tr_additional/TR-2002-04.pdf" rel="nofollow">Kutin'02</a>), but I think the first caveat still persists.</p>