6
$\begingroup$

Setting: Consider sampling two orthonormal vectors $\mathbf{u},\mathbf{v}$ in $\mathbb{R}^p$ (where $p\ge2$) from a "uniform" distribution over the $p$-dimensional sphere (alternatively, sample $\mathbf{u},\mathbf{v}\sim\mathcal{S}^{p-1}$ and then orthogonalize and normalize $\mathbf{v}$).

Let $\lceil p/2\rceil\le m\le p$.
Question: Can we upper bound the following expectation? $$ \mathbb{E}_{\substack{\mathbf{u},\mathbf{v}\sim\mathcal{S}^{p-1}:\\\mathbf{u}\perp\mathbf{v}}} \left(\mathbf{u}^\top\left[\begin{array}{cc} \mathbf{I}_{m}\\ & \mathbf{0}_{p-m} \end{array}\right]\mathbf{v}\right)^2 = \mathbb{E}_{\substack{\mathbf{u},\mathbf{v}\sim\mathcal{S}^{p-1}:\\\mathbf{u}\perp\mathbf{v}}} \left(\sum_{i=1}^{m}u_iv_i\right)^2 $$

Example: when $m$ is very close to $p$, the expectation should be very small, since the vectors are nearly orthogonal.

Direction: We thought about approximating this with just two independent Gaussian vectors and look for the concentration bounds when $p\to\infty$, but this seems perhaps too loose?

Observation: Since the vectors are orthogonal, we have $ \left(\mathbf{u}^\top\left[\begin{array}{cc} \mathbf{I}_{m}\\ & \mathbf{0}_{p-m} \end{array}\right]\mathbf{v}\right)^2 = \left(\mathbf{u}^\top\mathbf{v}-\mathbf{u}^\top\left[\begin{array}{cc} \mathbf{I}_{m}\\ & \mathbf{0}_{p-m} \end{array}\right]\mathbf{v}\right)^2 = \left(\mathbf{u}^\top\left[\begin{array}{cc} \mathbf{0}_{m}\\ & \mathbf{I}_{p-m} \end{array}\right]\mathbf{v}\right)^2$, and thus we can equivalently focus on $0\le m\le \lfloor p/2\rfloor$.

Any help and ideas would be greatly appreciated!

$\endgroup$
2
  • $\begingroup$ Related: mathoverflow.net/questions/360906/… $\endgroup$ Commented Aug 11, 2023 at 16:59
  • 1
    $\begingroup$ It turns out that this can be solved as a special case of Eq. (24) in "Integrals of monomials over the orthogonal group" (Gorin 2002). $\endgroup$
    – Itay
    Commented Aug 17, 2023 at 6:39

2 Answers 2

3
$\begingroup$

Denote $\alpha=\mathbb{E} u_1^2v_1^2$, $\beta=\mathbb{E} u_1v_1u_2v_2$. Then by the symmetry and linearity of expectation we have $$f(m):=\mathbb{E} (u_1v_1+\ldots+u_mv_m)^2=m\alpha+m(m-1)\beta.$$ We have $f(p)=0$, thus $\beta=-\alpha/(p-1)$, and $f(m)=\alpha m(p-m)/(p-1)$.

It remains to bound $\alpha$. Choose a vector $w=(w_1,\ldots,w_p)\in \mathcal{S}^{p-1}$ independent of $u,v$, then $\alpha=\mathbb{E} \langle u,w\rangle^2\cdot \langle v,w\rangle^2$, as the conditional expectation clearly does not depend on $w$ (here $\langle \cdot,\cdot\rangle$ stands for the inner product). On the other hand, the conditional expectation does not depend on the pair $u,v$ of orthogonal vectors $u,v$, thus we may take $u=(1,0,\ldots,0)$, $v=(0,1,\ldots,0)$, and $\alpha=\mathbb{E} w_1^2w_2^2$.

Next, we have $$1=\mathbb{E} \left(\sum_{i=1}^p w_i^2\right)^2=\alpha\cdot p(p-1)+p\cdot \mathbb{E} w_1^4,$$ thus $$\alpha=\frac{1-p\cdot \mathbb{E} w_1^4}{p(p-1)}.$$ To find $\mathbb{E} w_1^4$, we may think that $w=(w_1,\ldots,w_p)=(\xi_1,\ldots,\xi_p)/\sqrt{\sum \xi_i^2}$ where $\xi_i$ are i.i.d. standard normal. Then $$ \mathbb{E} w_1^4=\mathbb{E} \frac{\xi_1^4}{(\sum \xi_i^2)^2}=:\Theta $$ By some form of law of large numbers like Chernoff bound, the probability that $\sum \xi_i^2<p/2$ is exponentially small in $p$, that gives exponentially small contribution to the expectation $\Theta$. If $\sum \xi_i^2>p/2$, then $$\frac{\xi_1^4}{(\sum \xi_i^2)^2}<\frac{4}{p^2}\xi_1^4,$$ and since $\mathbb{E} \xi_1^4$ is a finite constant, we conclude that $\Theta=O(1/p^2)$. Thus $\alpha=1/p^2+O(1/p^3)$.

$\endgroup$
4
  • 1
    $\begingroup$ certainly, fixed this $\endgroup$ Commented Jun 22, 2023 at 6:58
  • $\begingroup$ Thank you Professor. However, if I am not mistaken, $\alpha=\mathbb{E} \langle u,w\rangle\cdot \langle v,w\rangle$ is still missing the square. Can we still introduce $w$ to the corrected $\alpha=\mathbb{E} {u_1}^2 {v_1}^2$ like the current answer does? $\endgroup$
    – Itay
    Commented Jun 22, 2023 at 7:14
  • $\begingroup$ fixed this too, please check $\endgroup$ Commented Jun 22, 2023 at 7:57
  • $\begingroup$ Great! Thank you very much! $\endgroup$
    – Itay
    Commented Jun 22, 2023 at 11:02
3
$\begingroup$

This is to complement the nice answer by Fedor Petrov by providing the exact expression for his $\alpha=Ew_1^2w_2^2$ and thus for the desired expectation $f(m)=\alpha m(p-m)/(p-1)$.

Just note that the random vector $(w_1^2,\dots,w_p^2)$ coincides in distribution with the random vector $\dfrac{(G_1^2,\dots,G_p^2)}{G_1^2+\dots+G_p^2}$, where the $G_i$'s are independent standard normal random variables, and hence the joint distribution of $w_1^2$ and $w_2^2$ is the Dirichlet distribution with parameters $1/2,1/2,p/2-1$. Therefore, after some simple calculations we get $$\alpha=Ew_1^2w_2^2=\frac1{p(p+2)}$$ (which is in agreement with Fedor Petrov's conclusion that $\alpha=1/p^2+O(1/p^3)$).

$\endgroup$
1
  • $\begingroup$ Nice! We've reached a similar conclusion using the fact that $w_{1}^{2}=\frac{X}{X+Y}\sim B\left(\frac{1}{2},\frac{p-1}{2}\right)$ and then used the fact that $\mathbb{E}_{w_{1}}\left[w_{1}^{4}\right]=\text{Var}\left[w_{1}^{2}\right]+\left(\mathbb{E}_{w_{1}}\left[w_{1}^{2}\right]\right)^{2}$. I guess your solution is somewhat more straightforward. $\endgroup$
    – Itay
    Commented Jun 22, 2023 at 15:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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