Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
pedantry: shouldn't it be variance \sigma^2 to avoid confusion with usual conventions? –  Yemon Choi Oct 26 '09 at 19:30
    
Yes, sorry. I've fixed it. –  Steve Flammia Oct 26 '09 at 19:58
add comment

4 Answers

up vote 5 down vote accepted

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).

share|improve this answer
    
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 –  Yemon Choi Oct 27 '09 at 4:29
add comment

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".

share|improve this answer
add comment

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.

share|improve this answer
    
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. –  Steve Flammia Oct 26 '09 at 20:01
    
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. –  Yemon Choi Oct 26 '09 at 20:53
    
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. –  Steve Flammia Oct 26 '09 at 22:09
    
Oh, and I should add: I'm mostly interested in an upper bound. So don't worry too much about the lower bound. –  Steve Flammia Oct 26 '09 at 22:22
    
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. –  Steve Flammia Oct 27 '09 at 1:47
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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