3
$\begingroup$

It's exercise 1.1 on p.2 of this book.

The goal is to is to show that, for some random matrix $Q \in \mathbb{R}^{n\times k}$ where $k and the columns of $Q$ are orthogonal (i.e. $Q^T Q = I$; and assuming $Q$ is uniformly distributed in whatever space it's a member of), then for $u \in \mathbb{R}^{n}$ and $v = \sqrt{n/k}Q^Tu$, the following holds: $$E(\|v\|^2)=\|u\|^2$$

I tried a few monte carlo experiments, and it does work out. It seems that $$E(QQ^T) = \textrm{diag}(k/n,\ldots,k/n)$$

If $Q$ is relaxed to be standard gaussian, I can work it out analytically. But I'm stumped how this works if $Q$ has an orthogonality constraint.

So how does $$E(\|v\|^2)=\|u\|^2$$ work?

  • 0
    If $Q^TQ=I$, then $P=QQ^T$ is an orthogonal projection from $n$-dimensional space to a $k$-dimensional subspace (=the span of columns of $Q$): $P^2=P$ and $Pu \perp u-Pu$ for all $u\in \mathbb{R}^n$. The effect of such a projection to the expected value of the squared norm is to scale it by a factor of $k/n$. W.r.t. a suitable coordinate system the projection just turns $n-k$ last coordinates of the vector $u$ to zero.2012-04-27
  • 0
    I thought that the above observation would answer your question, but the matrix $Q$ is fixed there, so I turned my answer into a comment. May be it can be fixed?2012-04-27
  • 0
    @JyrkiLahtonen "The effect of such a projection to the expected value of the squared norm is to scale it by a factor of $k/n$" I can see that this is the effect from monte carlo simulations. But I don't see how this is analytically. If you can answer this, I'd appreciate it.2012-04-27
  • 0
    Extend the columns of $Q$ to an orthonormal basis $\mathcal{B}$ of $\mathbb{R}^n$. Using the coordinates w.r.t. $\mathcal{B}$ we have $$P:u=(u_1',u_2',\ldots,u_n')\mapsto(u_1',u_2',\ldots,u_k',0,0,\ldots,0)=P(u).$$ On the set $||u||=1$ we have $E(u_i'^2)=1/n$, for all $i$. Therefore $E(\langle u, P(u)\rangle)=k/n$. Also $$||v||^2=\frac{n}{k}u^TQQ^Tu=\frac{n}{k}\langle u, P(u)\rangle,$$ so $$E(||v||^2)=1.$$ If your distribution of $u$ has spherical symmetry, then this should help.2012-04-27
  • 0
    @Jyrki: As I understand the question, $u$ is fixed; only $Q$ is random.2012-04-27
  • 0
    @joriki: you're right. For some reason I thought that both $u$ and $Q$ are random variables. I deleted my answer, when I realized that in my argument $Q$ was fixed. But we can always complete $Q$ to an orthogonal matrix. As an orthogonal transformation preserves the norms, it may be possible to switch the roles of $u$ and $Q$, and rescue my calculation. With your answer in place there is no need for that (and I would need to specify a density function on all the variables as well).2012-04-27

1 Answers 1

6

Your observation that $E(QQ^T) = \operatorname{diag}(k/n,\dotsc,k/n)$ points in the right direction. The expected value of the off-diagonal elements of $QQ^T$ vanishes by symmetry, since flipping the sign of a row of $Q$ preserves $Q^TQ=1$ but changes the sign of the off-diagonal elements of $QQ^T$. The diagonal elements must all be equal by symmetry, and $\operatorname{tr}QQ^T=\operatorname{tr}Q^TQ$ shows that they must be $k/n$.

Then by the cyclic invariance of the trace and the linearity of trace and expectation

$$ \begin{eqnarray} E\left(\lVert v\rVert^2\right) &=& E\left(v^Tv\right) \\ &=& E\left(\operatorname{tr}\left(v^Tv\right)\right) \\ &=& \frac nkE\left(\operatorname{tr}\left(u^TQQ^Tu\right)\right) \\ &=& \frac nkE\left(\operatorname{tr}\left(uu^TQQ^T\right)\right) \\ &=& \frac nk\operatorname{tr}\left(E\left(uu^TQQ^T\right)\right) \\ &=& \frac nk\operatorname{tr}\left(uu^TE\left(QQ^T\right)\right) \\ &=& \operatorname{tr}\left(uu^T\right) \\ &=& \operatorname{tr}\left(u^Tu\right) \\ &=& u^Tu \\ &=& \lVert u\rVert^2\;. \end{eqnarray} $$

Alternatively, you can argue as follows. Since permuting the columns of $Q$ preserves $Q^TQ=1$, the expected values of the squares of the components of $v$ are all the same by symmetry, so $E(\lVert v\rVert^2)$ is just $k$ times one of these expected values. A component of $v$ is $\sqrt{n/k}$ times the scalar product of a random unit vector with $u$. If we rotate to a basis in which $u$ has only one non-zero component, this scalar product becomes $\lVert u\rVert$ times that component of the random unit vector. By symmetry, the expected value of the square of a component of an $n$-dimensional unit vector is $1/n$, and the result follows.