4
$\begingroup$

Suppose I uniformly sample matrices X from the Gaussian Unitary Ensemble (GUE) with variance \sigma^2. Consider the Ky-Fan d norm, i.e. the sum of the singular values, of X. Let's call this Z=||X||_1. What is the distribution of Z as a function of the dimension d and the variance \sigma^2? Really, all I want are estimates of the mean and a good tail bound, so maybe also the second moment.

$\endgroup$
0

4 Answers 4

6
$\begingroup$

Let's normalise the variance of the entries to be $1$. Then GUE asymptotically obeys the semicircular law, i.e., the eigenvalues (which equal the singular values, as GUE is Hermitian), after dividing by $\sqrt{n}$, are distributed according to the law $\frac{1}{2 \pi} (4 - x^2)^{1/2}_+ dx$. So the Schatten $1$-norm (Ky Fan norm) should asymptotically equal $\sqrt{n}$ times n times the integral

\begin{equation*} \int \frac{|x|}{2 \pi} (4 - x^2)^{1/2}_+ dx, \end{equation*}

which Wolfram alpha tells me is $8/3 \pi$. So the answer is $n^{3/2} ( 8 / 3 \pi + o(1) )$ with probability $1-o(1)$. Using an explicit convergence rate for GUE, one can probably replace the $o(1)$ with $O(n^{-c})$ for some explicit constant $c>0$.

Getting the variance may be within current technology - it's some integral of two-point correlations of GUE, which are known - but somewhat tedious. Higher moments should also (in principle) be computable. My guess is that the limiting distribution will be asymptotically gaussian, but I might be wrong about this (the central limit theorem doesn't apply directly because the eigenvalues are correlated with each other).

$\endgroup$
1
  • $\begingroup$ Indeed, my only worry with using the semicircular law as heuristic was the non-uniform spacing of the eigenvalues - I gather this is all well understood by those who've thought about this more and better than I have, but thought it worth giving some cheap bounds that can be got by easy global arguments $\endgroup$
    – Yemon Choi
    Oct 27, 2009 at 4:29
2
$\begingroup$

More precise results along the lines of Yemon Choi's answers are in two papers by Szarek: "Spaces with large distance to $l^\infty$ and random matrices", and "Condition number of random matrices".

$\endgroup$
2
$\begingroup$

I'm not at all expert on random matrix stuff, but until someone more qualified pops up, would you be interested in some crude estimates on Z in the $n \to \infty$ asymptotic? Or do you really want something sharper in each dimension?

EDIT/UPDATE: OK, here's my hand-wavy argument, it's been a while since I did any probability theory, so caveat lector and all that.

I'm going to use the GOE just because that's the one I know better and to save me worrying about stray scaling factors.

The idea is that for any $n \times n$ matrices $S$ and $T$ we always have

$\Vert S\Vert_1 \Vert T \Vert_{\rm op} \geq |{\rm tr}(ST)|$

where the subscript 1 denotes Ky-Fan/Schatten 1-norm and the subscript "op" denotes usual operator norm. In particular, if $S=T$ is self-adjoint then

$\Vert S\Vert_1 \geq || S ||\_2^2\\, /\\, || S ||_{\rm op}$

Now when S is GOE(n,$\sigma^2$) then $n^{-2} \Vert S\Vert_2^2$ is strongly concentrated round its mean (which is $\sigma^2$) -- it's the average of a bunch of independent random variables so we could use variance estimates and Chebyshev, or probably some stronger exponential tail estimates.

Also, when S is GOE(n,$\sigma^2$) then $n^{-1/2} \Vert S\Vert_{\rm op}$ is strongly concentrated round $2\sigma$ - one can get exponential tail estimates, at least for an upper bound of $(2+\epsilon)\sigma$ for any positive $\epsilon$. I think this is folklore or a special case of Big Machinery, but as I said I have a more elementary proof, albeit one which is probably not original.

So, there is going to be a high probability (for $n$ large) that || S ||22 is bigger than $(1-\epsilon)\sigma^2n^2$, and there is going to be a high probability (for $n$ large) that $\Vert S\Vert_{\rm op}$ is less than $(2+\epsilon)\sigma n^{1/2}$. On the intersection of these two events you're going to find that

$\Vert S\Vert_1 \geq (1-\epsilon)n^2\sigma^2 / (2+\epsilon)\sigma n^{1/2}$

which gives the lower bound I was claiming.

$\endgroup$
5
  • $\begingroup$ As long as the estimate isn't too crude, then it should be fine. There is one obvious way to get an estimate, which is to use a bound on the 1-norm in terms of the 2-norm, picking up a dimensional factor along the way. I'd like to avoid that, if possible. $\endgroup$ Oct 26, 2009 at 20:01
  • $\begingroup$ OK, I can almost (modulo some CLT handwaving) show that, for any c\in (0,1/2), \sigma c \leq \liminf_n Z n^{-3/2} \leq \limsup_n Z n^{-3/2} \leq \sigma The upper bound is, as you allude to, just the 2-norm and Cauchy-Schwarz. The lower one would follow from some known upper bounds on the spectral radius in the GUE (and I have a reasonably elementary proof of the analogous sp. rad. bound for the GOE, I don't think the complex case is significantly different). Does this sound helpful? If so, I'll try to tighten up the argument - might post it on my blog if it checks out but looks a bit long. $\endgroup$
    – Yemon Choi
    Oct 26, 2009 at 20:53
  • $\begingroup$ Yes, that's helpful, thank you. Do I understand that correctly, that this implies the optimal scaling I can hope for with Z is n^{3/2}? I did a bit of numerics, and (at least for small n) it seemed like Z = O(n) up to maybe some log factors. (I'm ignoring a constant that depends on \sigma...) So this is a bit surprising. $\endgroup$ Oct 26, 2009 at 22:09
  • $\begingroup$ Oh, and I should add: I'm mostly interested in an upper bound. So don't worry too much about the lower bound. $\endgroup$ Oct 26, 2009 at 22:22
  • $\begingroup$ Wow, that's great! I can get the upper bound from here; I already estimated that one using 2-norm and Cauchy-Schwarz. I didn't realize that it was tight because my numerics was off, so I was dreaming about an impossible bound. Thanks for your help. $\endgroup$ Oct 27, 2009 at 1:47
1
$\begingroup$

Some vaguer thoughts: one way to try and get an intuitive handle on these kinds of global question, is to think of the not-quite-correctly named Wigner theorem on convergence to the semicircle distribution. That is, we know that if we scale the variance by 1/n then one gets convergence of the empirical spectral measure (in various senses) to a continuous density supported on [-2,2]. So there are going to be enough 'big' eigenvalues to drive up the values of the Schatten norms, in particular the sum of their absolute values should naively be O(n). This was when we scaled the entries by 1/\sqrt{n}, so to get a limit of the 1-norm it looks like we need a n^{-3/2} scaling.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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