A conjecture on the singular values of a Gaussian matrix

Before stating the problem, a bit of context is in order: although this open problem is about random matrices, it is motivated by work I am doing in the area of Theoretical Computer Science (see a paper here).

In this paper we describe an approximation algorithm for the little Grothendieck problem over the Orthogonal Group (since this post is about the conjecture itself and not the work that inspired it I don’t want to go into the Grothendieck problem — it is a really cool problem though, I’ll blog about it soon!). It turns out that the approximation ratio of this algorithm is guaranteed to be { \alpha_{\mathbb{R}}^2(d)} where {\alpha_{\mathbb{R}}(d)} is the average singular value of a Gaussian matrix.

Let me be more precise:

Definition 1 (of {\alpha_{\mathbb{R}}(d)}) Let {G_{\mathbb{R}}} be a {d\times d} random matrix with real iid entries {\mathcal{N}\left(0,\frac1d\right)}. Let {\sigma_k(G_{\mathbb{R}})} denote the {k}-th singular value of {G_{\mathbb{R}}}, then we define {\alpha_{\mathbb{R}}(d)} as

\displaystyle \alpha_{\mathbb{R}}(d) = \mathbb{E}\left[\frac1d\sum_{k=1}^d \sigma_k(G_{\mathbb{R}})\right].

 

One can similarly define this quantity in the complex field {\mathbb{C}} (which also corresponds to an approximation ratio of a slight variation of the algorithm proposed in here, this will appear in an update of the paper soon)

 

Definition 2 (of {\alpha_{\mathbb{C}}(d)}) Let {G_{\mathbb{C}}} be a {d\times d} matrix with complex iid entries {\mathcal{N}\left(0,\frac1d\right)}. Let {\sigma_k(G_{\mathbb{C}})} denote the {k}-th singular value of {G}, then we define {\alpha_{\mathbb{C}}(d)} as

\displaystyle \alpha_{\mathbb{C}}(d) = \mathbb{E}\left[\frac1d\sum_{k=1}^d \sigma_k(G_{\mathbb{C}})\right].

 

Broadly stated, the problem consists in understanding the sequences {\alpha_{\mathbb{K}}(d)} for {\mathbb{K} = \mathbb{R}} and {\mathbb{K} = \mathbb{C}}.

In the limit, {d\rightarrow\infty} the distribution of the eigenvalues is known. In fact, since that singular values of {G_{\mathbb{K}}} are the square-root of the eigenvalues of the Wishart matrix {G_{\mathbb{K}}(G_{\mathbb{K}})^T}, one can easily obtain the limit distribution of the singular values by the Marchenko-Pastur distrubtion (the limit distribution of the eigenvalues of a Wishart matrix). Interestingly this does not depend on whether {\mathbb{K} = \mathbb{R}} or {\mathbb{K} = \mathbb{C}}, in both cases the distribution of the singular values converges to the quarter-circle distribution given by

\displaystyle \mathrm{QC}(x) = \frac1{\pi}\sqrt{4-x^2}\mathbf{1}_{[0,2]}.

This means that

Lemma 3 For both {\mathbb{K} = \mathbb{R}} and {\mathbb{K} = \mathbb{C}},

\displaystyle \lim_{d\rightarrow \infty} \alpha_{\mathbb{K}}(d) = \int_0^2 x\frac1{\pi}\sqrt{4-x^2} = \frac{8}{3\pi} \approx 0.8488.

 

It seems that understanding {\alpha_{\mathbb{K}}(d)} for finite {d} is much more difficult. Nevertheless it is easy to compute {\alpha_{\mathbb{R}}(1)} since in that case, the singular value is simply the absolute value of a standard real gaussian random variable {X\sim \mathcal{N}\left(0,1\right)},

\displaystyle \alpha_{\mathbb{R}}(1) = \mathbb{E}|X| = \sqrt{\frac{2}{\pi}} \approx 0.7970.

This suggests that {\alpha_{\mathbb{R}}} is growing with the dimension.

The surprise comes when we try to do the same thing for {\mathbb{C}}. Note that{\alpha_{\mathbb{C}}(1)} is the expected absolute value of a standard complex gaussian random variable, if we separate the real and imaginary part they are independent and each has variance {\frac12} so {\alpha_{\mathbb{C}}(1)} is the expected norm of a {2} dimensional vector with real gaussian iid entries {\mathcal{N}\left(0,1/2\right)}. The distribution of the norm of {\sqrt{2}} times this vector is given by a {\chi} distribution with {2} degrees of freedom, whose mean is given by {\sqrt{2}\frac{\Gamma(3/2)}{\Gamma(1)}}. This means that

\displaystyle \alpha_{\mathbb{C}}(1) = \frac{1}{\sqrt{2}}\sqrt{2}\frac{\Gamma(3/2)}{\Gamma(1)} = \sqrt{\frac{\pi}4} \approx 0.8862.

This motivates the surprising conjecture:


Conjecture
 {\alpha_{\mathbb{R}}(d)} is monotonically increasing and {\alpha_{\mathbb{C}}(d)} is monotonically decreasing.

 

Both {\alpha_{\mathbb{R}}(d)} and {\alpha_{\mathbb{C}}(d)} can be written analitically in terms of (rather ugly, specially in the real case) integrals involving Laguerre polynomials. Althought these integrals can be computed, for each fixed {d}, using, e.g., Mathematica and I have verified that the sequences are respectively increasing and decreasing for {d\leq 50}, I haven’t been able to prove the Conjecture. Any ideas?

 

Advertisements

3 thoughts on “A conjecture on the singular values of a Gaussian matrix

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s