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?

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

Pingback: The little Grothendieck problem over O(d) | Relax and Conquer
Pingback: 18.S096: Principal Component Analysis in High Dimensions and the Spike Model | Relax and Conquer
Pingback: Luis Daniel Abreu proves the (complex version of) the Monotonicity of Singular Values Conjecture | Relax and Conquer

Relax and Conquer

A math research blog by Afonso S. Bandeira

A conjecture on the singular values of a Gaussian matrix

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

Leave a Reply Cancel reply

Share this:

Like this:

Related

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

Leave a Reply Cancel reply