Eigenvectors and eigenvalues from $X^TX$ to $XX^T$?

I have a $N\times D$ matrix, where $N<D$.

I wish to compute the eigenvalues and eigenvectors of $X^TX$, which is a $D\times D$ matrix. To speedup the MATLAB computations, I want to compute instead for $XX^T$, a $N\times N$ matrix. It is indeed quite fast, and I obtain $V$, whose each column is an eigenvector for $XX^T$, and $D$, a diagonal matrix holding $XX^T$'s eigenvalues.

How do I go from $V$ and $D$ to the eigenvalues and eigenvectors of $X^TX$?

The eigenvectors $X^TX$ can be computed as follows:

(1) Assume $v$ is an eigenvector $XX^T$ to eigenvalue $\lambda\ne0$. Then it holds $XX^Tv=\lambda v$, and $$X^TX(X^Tv) = \lambda (X^Tv).$$ Since $\lambda \ne0$, it follows $X^Tv\ne0$, hence $X^Tv$ is an eigenvector of $X^TX$ with eigenvalue $\lambda$.

(2) The eigenvectors to eigenvalue zero are the elements in the null space of $X$: $X^TX v=0$ implies $v^TX^TXv=\|Xv\|^2=0$, which is $Xv=0$.

That is, you obtain the eigenvectors of $X^TX$ from

• $X^Tv$ with $v$ eigenvector of $v$ of $XX^T$ to non-zero eigenvalue
• vectors in the null space of $X$
• Also the eigenspace dimensions are the same, for nonzero eigenvalues. – egreg Apr 23 '15 at 9:09

The eigenvalues are the same, only $X^TX$ has $0$ as an additional eigenvalue. Eigenvectors of the same eigenvalue in both spaces are mapped to one another by $X$ and $X^T$.