3
$\begingroup$

The problem of PCA basically boils down to finding the extremum of $$\psi(q) = q^TRq \tag 1$$ subject to constraint $$q^Tq = 1 \tag 2.$$

How I would go about solving it, is by differentiating the Lagrangian i.e. solving

$$\frac{d(q^TRq - {\lambda}(q^Tq - 1))}{dq} = 0 $$

which leads to $$Rq - {\lambda}q = 0$$

which is the eigenvalue problem to the covariance matrix $R$ as it should have appeared and the things are right into place.

But then I watched this lecture and the professor goes about with the first principle kind of way and I think that he messes it up big time but manages to get to the right answer. Here goes what he does:

At extremum:

$${\psi}(q+{\delta}q) = {\psi}(q)$$ $$(q+{\delta}q)^TR(q+{\delta}q) = q^TRq$$ $$q^TRq +{\delta}q^TRq + {\delta}q^TR{\delta}q + q^TR{\delta}q = q^TRq$$ removing ${\delta}q^TR{\delta}q$ as insignificant and cancelling $q^TRq$ from RHS $${\delta}q^TRq + q^TR{\delta}q = 0$$ Now as R is a covariance matrix and hence symmetric and for a symmetric matrix we have $a^TRb = b^TRa$ hence we get $${\delta}q^TRq = 0 \tag 3$$ and using eq 2 we also have $$((q+{\delta}q)^T(q+{\delta}q)) = 1$$ eliminating ${\delta}q^T{\delta}q$ and substituting $q^Tq = 1$ $${\delta}q^Tq = 0. \tag 4$$

Till now everything is okay. But now the professor does something which I cant seem to square with. He proceeds as follows:

At 41:30 he claims - combining eq3 and eq 4 we get: $${\delta}q^TRq - {\lambda}({\delta}q^Tq) = 0 \tag 5$$ which i don't think is a healthy way to combine the two equations as it introduces new solutions which do not satisfy the eq4 and eq5 but we should be okay as long as we keep that fact in mind (Any comments on this are welcome). Now he proceeds as: $${\delta}q^T(Rq - {\lambda}q) = 0 $$ and now the bummer, he claims that since ${\delta}q \neq 0$ we have $$Rq - {\lambda}q = 0 $$ thus taking us to the right final eigenvalue problem. Which is non-sensical. ${\delta}q$ could very well be orthogonal to $Rq - {\lambda}q$.

Please confirm if I am right in my criticism.

Instead, how could one have gone about solving it? Eq3 and eq4 tell me that ${\delta}q$ is orthogonal to the plane containing $q$ and $Rq$. How to move ahead and eliminate all the solutions but the ones where $q$ is an eigenvector of $R$ i.e. to reconcile this to the actual solution and collapse it to just containing $q$ such that $Rq = {\lambda}q$?

$\endgroup$
  • 3
    $\begingroup$ +1. Very interesting, I've never seen this derivation before. Note that $\delta q$ is arbitrary, hence you cannot assume that it's orthogonal to any particular vector (which is why you call this derivation "non-sensical"). $\endgroup$ – amoeba Sep 6 '17 at 14:23
  • 2
    $\begingroup$ You can find a justification of the not "healthy" manipulation by considering the transformations described in my answer at stats.stackexchange.com/a/301561/919. $\endgroup$ – whuber Sep 6 '17 at 14:40
5
$\begingroup$

Here is a slightly different way to carry out this argument. Consider equations (3) and (4) together: $$\delta q ^\top R q = 0 \\ \delta q ^\top q = 0$$

Eq. (4) says that $\delta q$ is orthogonal to $q$; indeed, this makes intuitive sense: $q$ is constrained to have unit length and so lies on the surface of the hyper-sphere. If $q$ is on its surface already, then only the infinitesimal movements in the orthogonal directions will remain on the surface.

Eq. (3) says that $\delta q$ is orthogonal to $Rq$. Note that infinitesimal vector $\delta q$ can be arbitrary, as long as satisfies the above constraint of being orthogonal to $q$. For any such $\delta q$ it must be that it is also orthogonal to $Rq$. The one and only way this can be true, is if $Rq$ is parallel to $q$.

Which makes $q$ an eigenvector of $R$ by definition.

$\endgroup$
  • 1
    $\begingroup$ yes i had connected this much after your comment on original question. Let me summarize to make sure i am on the same page as you - ${\psi}(q)$, though remains constant in the direction orthogonal to $Rq - {\lambda}q$, changes in all other directions. As long as ${\delta}q$ remains orthogonal to $q$, the perturbations to $q$ are allowed and hence it is not an extremum. the only places where ${\psi}(q)$ is constant in all the directions are where the $Rq - {\lambda}q$ becomes zero. Please confirm if i am making correct sense $\endgroup$ – MiloMinderbinder Sep 6 '17 at 22:26
  • $\begingroup$ Sorry, I am not sure I follow your comment. Let me say it this way: if $Rq$ is not parallel to $q$ (i.e. if $q$ is not an eigenvector), then you can choose $\delta q$ to be orthogonal to $q$ but NOT orthogonal to $Rq$. With this specific choice of $\delta q$, Eq. (4) will hold but Eq. (3) will not hold. Hence, if $q$ is not an eigenvector, then $\psi(q)$ cannot be an extremum. $\endgroup$ – amoeba Sep 6 '17 at 22:49
  • $\begingroup$ 'if $Rq$ is not parallel to $q$ (i.e. if $q$ is not an eigenvector), then you can choose ${\delta}q$ to be orthogonal to $q$ but NOT orthogonal to $Rq$' -why cant i choose${\delta}q$ orthogonal to the plane containing $Rq$ and $q$. What i am saying is that it can be chosen but that isnt how the extremum is going to be found. We need to find $q$ such that ${\psi}(q)$ is at extremum, which means its derivative goes to zero at every choice of ${\delta}q$ subject to only one constraint that $q$ remains a unit vector. $\endgroup$ – MiloMinderbinder Sep 6 '17 at 23:45
  • $\begingroup$ just for visualization's purpose When we force ${\delta}q$ that is orthogonal to the plane containing $Rq - {\delta}q$ and then find $q$ we find $q$ where ${\psi}(q)$ is maybe shaped like a saddle or a cylinder cut along its height and that direction of no change for ${\psi}(q)$ being the direction orthogonal to the plane containing $Rq - {\delta}q$ $\endgroup$ – MiloMinderbinder Sep 6 '17 at 23:54

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.