So I have matrix A which has (m×d) dimension and X = A.A^T
My X has d non-zero distinct eigenvalues and m > d
Usually I compute eigendecomposition matrix which has (mxm) dimension to find eigendecomposition of X and from there I can find eigenvalues and eigenvector of X. But my m is larger than d, so it is slower.
Assume I have an eigendecomposition “black box” subroutine (I'm not using SVD as a black box), how can I find eigenvalue and eigenvector of X using eigendecomposition matrix which has (d×d) dimension?
Suppose $y$ is an eigenvector of $A^{\intercal}A$ so that $A^{\intercal}Ay=\lambda y$. Let $x=Ay$. Then, $$ AA^{\intercal}x=A(\lambda y)=\lambda Ay=\lambda x $$ and hence $x$ is an eigenvector $AA^{\intercal}$. In particular, this implies that $A^{\intercal}A$ and $AA^{\intercal}$ share $d$ (possibly nonzero) eigenvalues. The remaining eigenvalues of $AA^{\intercal}$ are guaranteed to be zero.
This means that we can compute the eigenvalues $\lambda_{1},\ldots,\lambda_{d}$ and eigenvectors $y_{1},\ldots,y_{d}$ of $A^{\intercal}A$ and obtain the corresponding pairs for $AA^{\intercal}$ by computing $x_{i}=Ay_{i}$ for each $i=1,\ldots,d$.