Random matrix with given singular values

Question

Let $\sigma_1\geq\sigma_2\geq...\geq\sigma_n\geq0$ be any deterministic sequence of positive real numbers such that $\sum_{i=1}^n\sigma_i^2=1$. Let $$D=diag\{\sigma_1,...,\sigma_n\}\in\mathbb{R}^{n\times n}$$ be a diagonal matrix of size $n\times n$.

Let $U$ and $V$ be two independent random matrices uniformly distributed on the orthogonal group $O(n)$. Then we form a random matrix as follows: $$A=UDV^T$$ Therefore, $A$ is a random matrix with given singular values and the distribution is orthogonally invariant. Now we define a quantity that measures how far away is $A$ from a diagonal matrix: $$f_{\sigma}(A)=\sum_{1\leq i\neq j\leq n}A_{ij}^2=\sum_{1\leq i\neq j\leq n}\left(\sum_{k=1}^n\sigma_kU_{ik}V_{jk}\right)^2=1-\sum_{i=1}^n\left(\sum_{j=1}^n\sigma_jU_{ij}V_{ij}\right)^2$$ which is just the sum of squares of all off-diagonal elements of $A$, the smaller $f_{\sigma}(A)$ is, the "more diagonal" $A$ is. Note the dependency of $f$ on the given singular values $\sigma$.

I'm interested in the following quantity: $$g_{\sigma}(t)=\frac{\mathbb{P}\left(f_{\sigma}(A)\leq 2t\right)}{\mathbb{P}\left(f_{\sigma}(A)\leq t\right)}$$ where $0<t<1/2$.

I have the following 2 conjectures:

1. For $n\geq 5$, for any $0<t<1/2$, $g_{\sigma}(t)$ is maximized when $\sigma_1=...=\sigma_n=1/\sqrt{n}$.
2. There exists a constant $C>1$ independent of $t, \sigma$, such that $g_{\sigma}(t)\leq C^{n^2}$

I believe they should be correct but I have no clue of how to prove them. Any suggestions and discussions are appreciated. What kind of tools could possibly be useful?

I have a feeling that existing literature in random matrix mainly focus on going from the matrix to eigenvalues or singular values, ignoring the eigenvectors or singular vectors. I do not see results about going from given spectrum to the matrix.

Answer 1

Conjecture 1 is false. Here is the counterexample for $n=2$.
_{this is the conjecture 1 as originally given by the OP; I see that it has now been changed.}

I take $n=2$, set $\sigma_1=\cos\alpha$, $\sigma_2=\sin\alpha$, with $0\leq\alpha\leq\pi/4$, and parameterize the orthogonal matrices as $$U=\begin{pmatrix} \cos\phi&\sin\phi\\ -\sin\phi&\cos\phi \end{pmatrix},\;\;V=\begin{pmatrix} \cos\phi'&\sin\phi'\\ -\sin\phi'&\cos\phi' \end{pmatrix}.$$ The Haar measure on $\text{SO}(2)$ is a uniform distribution of the angles $\phi,\phi'\in(0,2\pi)$, with $\phi$ independent of $\phi'$. I calculate $A=U\,\text{diag}\,(\sigma_1,\sigma_2)V^T$ and evaluate $$f_\alpha=A_{12}^2+A_{21}^2=\tfrac{1}{2} (1-\sin 2 \alpha \sin 2\phi \sin 2\phi'-\cos 2\phi \cos 2\phi').$$

Let me now compare the two extreme cases $\alpha=\pi/4$ and $\alpha=0$, $$f_{\pi/4}=\sin^2(\phi-\phi'),\;\;f_0=\tfrac{1}{2}(1-\cos 2\phi\cos 2\phi').$$ The corresponding probability distributions are $$p_{\pi/4}(f)=\frac{1}{\pi}f^{-1/2}(1-f)^{-1/2},$$ $$p_0(f)=\frac{4}{\pi^2} \int_0^{\arccos|1-2f|}\frac{d\phi}{\sqrt{\cos^2 \phi-(1-2f)^2}}.$$ (The expression for $p_0(f)$ is an elliptic integral.) I checked both distributions numerically (by generating random $\phi,\phi'$) and they do seem to be correct, see the histograms:

Because $p_{\pi/4}(f)$ has a peak at $f=0$, while $p_0(f)$ has a peak at $f=1/2$, the ratio $g_\alpha(t)$ of cumulative distributions at $2t$ and $t$ is larger for $\alpha=0$ than it is for $\alpha=\pi/4$, for all $0<t<1/2$. Here is a plot that compares the two, blue is for $\alpha=\pi/4$ and gold is for $\alpha=0$.

So this is a counter example to conjecture 1, because $\alpha=\pi/4$ corresponds to $\sigma_1=\sigma_2=1/\sqrt n$ for $n=2$.

Answer 2

What you want for 2- seems to me similar to a large deviation result (https://en.wikipedia.org/wiki/Large_deviations_theory) of speed $n^2$ for the diagonal term $$\frac{1}{n^2}\log\mathbb{P}(\sum_i A_{ii}^2\geq s)\approx I(s) $$

with some function $I(s)<0$. Indeed if so we have $$\log (g(t)) \approx n^2 (I(1-2t)-I(1-t)) $$ and then you can choose $\log C=\inf (I(1-2t)-I(1-t))$

This is not true for the case $\sigma=(1,0,\cdots,0)$ but we have a better upper bound. Here for $A_{11}^2\geq s$ it is enough to ask that $U_{11}\geq s^{1/4}$ and $V_{11}\geq s^{1/4}$. The first column of $U$ is a random vector chosen uniformly on the sphere $\mathbb{S}^{n-1}$ and a good way to construct it is using a set of iid Gaussian variables $Y_i$ and write $$ U_{i1}:=\frac{Y_i}{\sqrt{\sum_{j}Y_j^2}} $$ We use here that the direction of a Gaussian vector is isotropic on $\mathbb{S}^{n-1}$. Then $$ \mathbb{P}(U_{11}\geq s^{1/4})\geq \mathbb{P}(Y_1\geq 2s^{1/4},\forall j\geq2: |Y_j|\leq s^{1/4}/\sqrt{n})\geq C\left(\frac{c}{\sqrt{n}}\right)^{n-1}$$ for some constant $c$ and $C$. And then $$\log(\mathbb{P}(A_{11}^2\geq s)\geq \log\left( \mathbb{P}(U_{11}\geq s^{1/4})\mathbb{P}(V_{11}\geq s^{1/4})\right)\geq (n-1)(\log n+c')$$ which is a slower speed that $n^2$. As a conclusion we have $$g_{(1,0,\cdots,0)}(t) \leq (C')^{n\log n} $$ for some $C'>1$.

For the case $\sigma = (\frac{1}{\sqrt{n}},\cdots,\frac{1}{\sqrt{n}})$, I think one should be able to obtain the large deviation principle with speed at least $n^2$. Here we only consider $U\in \mathcal{O}(n)$ chosen uniformly as multiplication by $V^{T}$ doesn't modify the Haar measure. The construction of the fist column of $U$ is similar as above and we should at least obtain $$ \mathbb{P}(U_{11}^2\geq s)\leq \exp(n\tilde{I}(s))$$ for some $\tilde{I}<0$ as large deviation principle for $\sum_j Y_j^2$ are well known (Cramer Theorem). We now condition on $U_{11}$ and write the matrix $$\begin{pmatrix} U_{11} & Y \\ \tilde{Y} & U'\end{pmatrix} $$ Because $Y$ is rotation invariant, so is $U'$. Moreover because for any vector $v=(0,v_2,\cdots,v_n)^T$ we have $\|Uv\|^2=|\langle Y,(v_2,\cdots,v_n)\rangle|^2+\|U'(v_2,\cdots,v_n)\|^2\geq \|U'(v_2,\cdots,v_n)\|^2 $, we are reduce to the original problem on $U'$ for some $\sigma'=\frac{1}{\sqrt{n}}(\sigma_1',\cdots,\sigma_{n-1}')$ with $\sigma_i'\leq 1$ for all $i$. Therefore $$\mathbb{P}(\sum_{j\leq n-1}(U_{jj}')^2\geq (n-1)s)\leq \mathbb{P}(\sum_{j\leq n-1}(U_{jj}'')^2\geq (n-1)s)$$ where $U''$ is chosen uniformly on $\mathcal{O}(n-1)$ and we are reduce to system of size $n-1$. By direct iteration we get
$$ \mathbb{P}(U_{11}^2\geq s)\mathbb{P}(U_{22}^2\geq s)\cdots \mathbb{P}(U_{nn}^2\geq s)\leq \exp(n\tilde{I}(s))\exp((n-1)\tilde{I}(s))\cdots \exp(\tilde{I}(s))\\ =\exp(n(n-1)\tilde{I}(s)/2) $$ which reveal the large deviation with $n^2$ speed.

One can use $\mathbb{P}(\sum_{i\leq n}U_{ii}^2\geq s n)\leq \mathbb{P}(\exists K\subset [N]:|K|\geq sn/2:\forall i\in K : U_{ii}^2\geq s/2)$ to finish the proof with an union bound