1
$\begingroup$

Let $A$ be a gaussian matrix of size $d \times n$ where all the coefficients are drawn i.i.d. from $ \mathcal{N}(0, 1)$ and denote by $s_{\text{max}}$ its largest singular value.

Theorem 2.6 of http://www-personal.umich.edu/~rudelson/papers/rv-ICM2010.pdf mentions that : $$ \mathbb{E} (s_{\text{max}}) \leq \sqrt{n}+\sqrt{d} $$ Hence : $$ \mathbb{E} (\frac{s_{\text{max}}}{\sqrt{n}}-1 ) \leq \sqrt{\frac{d}{n}} $$

I'm looking for a non-asymptotic upper-bound on $ s_{\text{max}}^2 $ that would look like : $$ \mathbb{E} (~| \frac{s_{\text{max}}^2}{n}-1 |~) \leq C~ \frac{d}{n} $$ C being a constant. This is the same as bounding $ \frac{AA^T }{n} - I $, and the Frobenius norm already gives a bound in order of $ \frac{d^2}{n} $.

$\endgroup$
3
$\begingroup$

Say $d\le n$. For an upper bound on the size of $s_{\max}$, for a matrix with sub-Gaussian entries we actually have the upper tail bound $P(s_{\max}\ge C\sqrt{n}) \le e^{-cn}$ for some absolute constants $C,c>0$. See for instance Fact 2.4 here (which gives explicit constants):

http://www-personal.umich.edu/~rudelson/papers/rand-matr.pdf

This gives $E(s_{\max}^2)\le C'n$ for some constant $C'>0$.

If you want a bound on the variance of $s_{\max}$, note that a bound of constant order follows quickly from Gaussian concentration. Indeed, $s_{\max}$ is a 1-Lipschitz function on the space of $d\times n$ Gaussian matrices with the Hilbert-Schmidt norm. Of course, the Tracy-Widom law suggests a better than constant-order bound.

Edit: for your new question about whether we have $\mathbb{E}(|\frac{s_{\max}^2}{n}-1|)\le C\frac{d}{n}$, note that this is false for $d=1$ (and sufficiently large $n$). In this case $s_{\max}^2$ is just the squared norm of a Gaussian vector of length $n$, so $\mathbb{E}(|s_{\max}^2-n|)$ is of order $\sqrt{n}$.

$\endgroup$
1
$\begingroup$

For a non-asymptotic result, you could just use the exact distribution of $s^2_{\rm max}$ given in Distribution of the largest eigenvalue for real Wishart and Gaussian random matrices... (Marco Chiani, 2014). These exact distributions are mixtures of gamma distributions. For large $d$ the distribution of $s^2_{\rm max}$ tends to the Tracy-Widom distribution, which is itself quite well approximated by a single gamma distribution, see equation 48 in that paper.

$\endgroup$

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.