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