13
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Is uniform distribution on $O(n)$ defined by the euclidean measure on spheres ? $\endgroup$ – Claude Chaunier Jan 7 at 18:43
  • $\begingroup$ @ClaudeChaunier It is the Haar measure on the orthogonal group. $\endgroup$ – neverevernever Jan 7 at 19:46
2
+25
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I got a somewhat different expression for $f$... However, from a geometric perspective, if $\alpha=0$, the dimension of the problem is essentially reduced, the enlargement of the sublevel set of $f$ on the orthogonal group should be smaller. $\endgroup$ – neverevernever Jan 7 at 19:45
  • $\begingroup$ This is very counter intuitive and it is surprising that $\alpha=0$ consistently beats $\alpha=\pi/4$. Could the conjecture be the other way around, which means the most unbalanced case, $\sigma_1=1$ will dominate all other $\sigma$? $\endgroup$ – neverevernever Jan 8 at 2:01
  • $\begingroup$ here is my intuition: If I partition an orthogonal matrix $M$ into four blocks, $M_{11}$, $M_{12}$, $M_{21}$, and $M_{22}$, and consider the singular values of an off-diagonal block, then the distribution of these singular values peaks at 0 and at 1 when $M$ is uniformly distributed in ${\rm O}(n)$. Now if you choose the balanced case, then $M=UV^T/\sqrt n$ has a uniform distribution in $\text{O}(n)$. This means that $M$ is either largely off-diagonal (peak at 0) or largely diagonal (peak at 1), with equal probability. The peak at 0 skewes your $g$-ratio to small values. $\endgroup$ – Carlo Beenakker Jan 8 at 7:33
  • $\begingroup$ I also did some simulation. However, for $n>2$, the peak at $0$ no longer exists. Also, as $n$ gets larger, the distribution of $f$ for the two extreme cases gets closer and closer. $\endgroup$ – neverevernever Jan 8 at 21:36
  • $\begingroup$ Also, my simulation result shows that as $n$ even larger, say, > 5, the distribution of balanced case is more concentrated while the unbalanced case is slightly more spread out. $\endgroup$ – neverevernever Jan 8 at 21:46
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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