Let $A\in\mathbb{R}^{m\times d}$ matrix with iid standard normal entries, and $m\geqslant d$, and define $S=A^T A$.

I want to have a tight upper bound for $\sum_{k=1}^d \lambda_k^2$, where $\lambda_1,\dots,\lambda_d$ are the eigenvalues of $S$.

What I tried:

  • We know that (see e.g. Corollary 5.35 in Vershynin's notes), for $A\in\mathbb{R}^{m\times d}$, for any $t\geqslant 0$, with probability at least $1-2\exp(-\Omega(t^2))$, it holds: $$ \sqrt{m}-\sqrt{d}-t \leqslant \sigma_{min}(A)\leqslant \sigma_{max}(A)\leqslant \sqrt{m}+\sqrt{d}+t. $$ Simply ignoring $\sqrt{d},t$ terms (say I am in the regime $m\gg d,t$), this yields $\lambda_i(A)<m^2$, and thus, the sum above is upper bounded by $m^2d$.
  • We also have the following: $$ \sum_{k=1}^d (\lambda_k - m) = \sum_{i =1}^m \sum_{j=1}^d (A_{ij}^2-1), $$ which is sum of sub-exponential random variables, and thus, by a Bernstein-type bound, $\sum_{k=1}^d \lambda_k \leqslant md+\omega(\sqrt{md})$, for some function $\omega(\sqrt{md})$ growing faster than $\sqrt{md}$.
  • The sum above is simply the trace of $S^2=A^TAA^TA$.

I'm new to random matrix business, so any help is greatly appreciated.


I will assume $m=\alpha_d ds$ with $\alpha_d\to \alpha \in [1,\infty)$ independent of $d$. The case $\alpha\to\infty$ is actually easier.

Define $Z=d^{-1} m^{-2} \sum_{i=1}^d \lambda_i^2$. Then $Z$ converges a.s. to $\int x^2 d\mu_\alpha(x)$ where $\mu_\alpha$ is the Pastur-Marchenko distribution of parameter $\lambda=1/\alpha$, see https://en.wikipedia.org/wiki/Marchenko%E2%80%93Pastur_distribution

  • $\begingroup$ Ofer, thanks for the answer. Sorry, if it is a trivial question: How to handle the case $\alpha\to+\infty$ (more precisely, when $d\to+\infty$ and $d=o(m)$)? $\endgroup$ – kawa Jun 17 '19 at 20:13
  • $\begingroup$ And also why the normalization is by $d^{-1}m^{-2}$? I understand that MP law requires $\frac1m$ normalization, and you get an extra for $d$, but why $d^2$? $\endgroup$ – kawa Jun 17 '19 at 20:19
  • $\begingroup$ That is the limiting case, in which the limit empirical measure is a dirac at 1.... $\endgroup$ – ofer zeitouni Jun 17 '19 at 20:19
  • $\begingroup$ and the normalization is as in the wikipedia page I quoted. You get $1/d$ from the empirical measure and $1/m^2$ from the normalization of the entries (you are taking the square of the MP matrix...) $\endgroup$ – ofer zeitouni Jun 17 '19 at 20:22

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.