6
$\begingroup$

In this blog figure 4 shows that the principal components of a random walk are sinusoidal with increasing frequency for decreasing eigenvalue. Is there an intuitive way of understanding this?

If I generate two independent random walks with a mean of zero, why is there a covariance (or correlation) between these trajectories in the first place?

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
5
$\begingroup$

I actually recently wrote a paper on this subject which will appear at NIPS 2018: https://arxiv.org/abs/1806.08805

My collaborator and I proved that in the limit of an infinite number of dimensions the projection of a random walk onto any PCA component is a sinusoid. You are welcome to read the paper for the proof, but perhaps I can attempt a slightly more intuitive explanation.

The random walk process is a translation invariant process. No matter how many steps you take and how far away you get from the origin, the process that determines the next step is exactly the same. (This is in contrast to an Ornstein-Uhlenbeck process, for example, which is a random walk in a quadratic well. In this case the process that determines what your next step will be depends on your distance from the origin.)

Now, the eigenfunctions of any translation invariant operator are Fourier modes. Why is this? Well, in order to be translation invariant, the eigenfunctions need to be periodic, and in order to be an orthogonal basis, they need to be mutually orthogonal. The set of functions that satisfies these properties is the Fourier basis.

As for your second question about two independent random walks seeming to be correlated, this is just an illusion. Although the projection of the trajectory of both random walks onto their first PCA component will be a cosine, the direction of the first PCA component will be completely random. An an analogy, if you do two random walks, each of 10^6 steps, you can be quite sure that both will end up at a distance of about 1000 from the origin. But the two walks had nothing to do with each other, and furthermore the direction that the walk happened to go will be different each time.

Improve this answer
$\endgroup$
14
  • 2
    $\begingroup$ +1. Very nice! Congratulations on having a paper accepted to NIPS. Actually your paper is more interesting than all six papers I had to review for NIPS this year :) Regarding intuition, it's worth noting that Fourier modes appear every time one does PCA of some roughly translation-invariant smooth data. One well-known example is PCA of natural images (e.g. ImageNet). But it happens quite frequently and I recall quite some confusion about it in some fields; see e.g. nature.com/articles/ng.139 for discussion. $\endgroup$
    – amoeba
    Commented Sep 19, 2018 at 20:57
  • 1
    $\begingroup$ Hi @vbip! I believe you have caught a typo. I think you are correct that it should be $2(1 + \gamma + \gamma^2)$. You'll notice in the following equation (21) that the first term in the inverse of the eigenvalue is $2(1 + \gamma + \gamma^2)$ which only makes sense if the previous equation is missing that last factor of 2 on the $\gamma^2$. I went ahead and redid the math and got $2(1 + \gamma + \gamma^2)$ like you. $\endgroup$
    – J. O'Brien Antognini
    Commented Nov 6, 2021 at 20:14
  • 1
    $\begingroup$ As for your other questions, I don't remember explicitly deriving $\textbf{M}^{-1}$, but if you try multiplying $\textbf{M}\textbf{M}^{-1}$ for a 6x6 matrix, I think you can convince yourself that it works. Basically the fact that $\textbf{M}^{-1}$ is banded Toeplitz means that you're only ever considering the effect of neighboring elements of $\textbf{M}$ on each other. You're basically always doing $\gamma^k + \gamma^{k-1} (-\gamma) = 0$, except along the diagonal (or above it, where everything is zero). $\endgroup$
    – J. O'Brien Antognini
    Commented Nov 6, 2021 at 20:19
  • 1
    $\begingroup$ No, I don't believe any of the rest of the paper would be affected. For Eqs. 17 & 18, you could check out p. 293 of Deep Learning by Goodfellow et al.: deeplearningbook.org/contents/optimization.html Alternatively, eqs. 1 & 2 of Sutskever et al.: cs.toronto.edu/~hinton/absps/momentum.pdf $\endgroup$
    – J. O'Brien Antognini
    Commented Nov 7, 2021 at 17:20
  • 1
    $\begingroup$ Sorry for the delay! The $\bf{v}_t$ in Eqs. 17 & 18 are unrelated to the eigenvectors defined previously. The $\bf{v}_t$ are simply a "velocity" term in the momentum update equation. $\bf{v}_t$ is initialized to 0 at time 0 and and then its value at later times is governed by Eq. 17. $\endgroup$
    – J. O'Brien Antognini
    Commented Nov 28, 2021 at 2:21

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.