7

I understand that Multidimensional scaling (MDS) is same as doing Principal Components analysis (PCA) if Euclidean distance is used, this is known as Metric MDS. But I came across this in a book that "it has been shown (Chatfield and Collins 1980) that the eigenvalues of $XX^T$ (unnormalised outer product matrix) are equal to the eigenvalues $X^TX$ (unnormalised inner product matrix) and eigenvectors of $XX^T$ and $X^TX$ are related by a linear transformation. "

Note, that X denotes a matrix of data, with $n$ features (rows) and $m$ instances (columns).

Now I am unable to get this Chattield and Collins book anywhere, and I can understand that the eigenvalues are equal. But how are the eigenvectors of PCA and metric MDS related to each other ?

user76170
  • 639
  • 2
  • 8
  • 9
  • 1
    When you left-multiply the eigenvector equation $(XX')b=\lambda b$ by $X'$, factor the scalar $\lambda$ through, and write $e=X'b$, you get $(X'X)e=\lambda e$, immediately obtaining the Chatfield & Collins results. – whuber Jun 03 '13 at 14:25
  • Left multiplying by $\mathbf{X}^T$, I obtain $$\mathbf{X}^T \mathbf{X} \mathbf{X}^T \mathbf{b} = \lambda \mathbf{b}$$. After this, what happens ? What do you mean by "factor the scalar $\lambda$ through ? – user76170 Nov 04 '13 at 10:29
  • When the ground ring is commutative--as it is when you are using real or complex numbers--the order of multiplication does not matter. That fact will be needed to simplify the right hand side after you remember that it, too, needs to be left-multiplied by $X'$ in order to maintain the equality. – whuber Nov 04 '13 at 20:16

1 Answers1

6

I find it helpful to consider the singular value decomposition for questions like this with the assumption that $X$ is a real matrix. Writing $X = UDV^T$, we can see that $XX^T = UD^2U^T$ and $X^TX = VD^2V^T$. As we can see, the eigenvalues of both $XX^T$ and $X^TX$ are contained in the diagonal matrix $D^2$ and are indeed equal. Also, we see that the matrix of eigenvectors of $XX^T$ is $U$, while the matrix of eigenvectors of $X^TX$ is $V$.

Because $$ X^TU = VDU^TU = VD, $$ we have the relationship $X^TU = VD$, similar to that pointed out by whuber.

Assuming $D$ is nonsingular, two additional properties that prove to be quite useful are:

$$ \begin{align} U &= XVD^{-1}\\ V &= X^TUD^{-1}. \end{align} $$

ramhiser
  • 1,683
  • 14
  • 14
  • @ John : I understood that till the matrix of eigenvectors part, but after that how do you conclude $X^TU = VD$ ? – user76170 Jun 19 '13 at 16:37
  • I updated my answer to clarify the conclusion. – ramhiser Jun 19 '13 at 21:21
  • I understood your derivation of $\mathbf{X}^T \mathbf{U} = \mathbf{V} \mathbf{D}$, so we can write $\mathbf{U} = {(\mathbf{X}^T})^{-1} \mathbf{V} \mathbf{D}$. But now I am again stuck, this eqn is fine theoretically, but practically how do you find ${\mathbf{X}^T}^{-1}$, since $\mathbf{X}$ is rectangular. Surely, there must be some other way. – user76170 Nov 04 '13 at 10:43
  • Because $X$ is rectangular, it does not have an inverse. I have updated my answer to answer your follow-up question. To calculate $U$, we start with $XV = UD$ and postmultiply each side by $D^{-1}$. – ramhiser Nov 04 '13 at 20:08