PCA for image analysis - Eigendecomposition VS SVD

Question

I have learned about two different ways of doing PCA, one using Eigendecomposition and the other (IMO more intuitive) using SVD. Although both are "just" a change of basis, I struggle to see how one can use Eigendecomposition for dimensionality reduction in the context of object recognition.

Situation:

Given $n$ images $f_i$ , each written as an $m$ vector (training set) and centered around $0$, we want to find a smaller representation using Eigenfaces (i.e. using principal components of a face images).

Using SVD:

1. Write the images as columns into a matrix $M := [f_1, f_2, ..., f_n]\in \mathbb{R}^{m \times n}$.
2. Apply (economical) SVD to get $U \in \mathbb{R}^{m \times n}, \Sigma \in \mathbb{R}^{n \times n}, V^T \in \mathbb{R}^{n \times n}$. Note that $U$ holds orthonormal vectors in columns (our principal components), while $\Sigma \cdot V^T $ holds our weights for each such vector.
3. To reduce dimension, we just truncate the matrices: keep first $k$ columns of $U$, the upper left $k \times k$ submatrix of $\Sigma$ and the first $k$ rows of $V^T$. Call them $U_k, \Sigma_k, V^T_k$ respectively and $W_k := \Sigma_k \cdot V^T_k$.
4. For any "new" input image $g$ centered around $0$, to check how similar it is with any stored image $f_i$, we can just compute $||(W_k)_{:,i} - U_k^T \cdot g||_2$. Hence, we only now need to do $\mathcal{O}(n \cdot k)$ operations rather than $\mathcal{O}(n \cdot m)$ to compare $g$ with our dataset $M$.

This approach makes sense, as I can really see where the $W_k$ come from. I also find it intuitive how to reconstruct an (approximation of an) image given its weight vector $w$, as all we need to do is multiply it from the left with $U_k$.

If we want to do an alternative approach using Eigendecomposition, I don't see how the above goal is achieved. Based on what I know, I would compute PCA using Eigendecomposition the following way:

1. Same as SVD
2. Do autocorrelation $C_M := \frac{1}{n} M M^T$
3. Diagonalize $C_M$, get $\Phi, \Lambda$ out, where $\Phi$ holds the Eigenvectors in columns, $\Lambda$ is diagonal matrix of eigenvalues $\lambda_i$.

Problem:

The issue I am having is that the PCA using Eigendecomp. is performed on the autocorrelation matrix and not on the original data. This indirection step makes me lose track of:

1. How to compare similarity of a new image $g$ with the existing ones, similar to step (4) of SVD-based PCA.
2. How to go back from PCA to reconstructed images. For that, I reckon we would need to reverse Autocorrelation, which I am not sure how to do.

So far, all ressources I checked out only use Eigendecomposition as a didactic tool and then quickly switch over to the SVD based approach. They include but are not limited to:

• Math Stackexchange
• Lecture notes
• A Tutorial on Principal Component Analysis

Answer 1

Maybe already a late answer. Just in case you still need it and also as a review for myself.

It might be easier to understand if we call $C_M$ "variance-covariance matrix" rather than "autocorrelation" (as the data is already centered around 0, these 2 concepts make no difference).

$C_M$ actually shows the significance of variations wrt. the mean of each pixel and correlations between different pixels. And the significance of variations somehow indicates how much information each pixel holds for the whole image.

If we look into detail (remember $U, V, \Phi$ are all orthogonal, $\Sigma, \Lambda$ are both diagonal): $$\begin{align} C_M & = \frac{1}{n-1}MM^T \text{ (unbiased)} \\ & = \frac{1}{n-1}U\Sigma V^TV\Sigma^TU^T \\ & = U\frac{\Sigma \Sigma^T}{n-1}U^T \\ & = \Phi \Lambda \Phi^T \end{align}$$ Thus, we can write: $$\begin{align} U & = \Phi, \Phi \in \Bbb{R}^{m \times n} \\ \Lambda & = \frac{\Sigma \Sigma^T}{n-1}, \Lambda \in \Bbb{R}^{n \times n} \end{align}$$ So what you get from doing SVD on $M$ and EVD on $C_M$ are somehow the same, as the eigen values only tell contribution of components, the scale is not really relevant.

Now we are going to reconstruct the image:

1. First, we need to project $M$ from pixels to the feature space: $$M_\Phi = M\cdot\Phi, M_\Phi \in \Bbb{R}^{m \times n}$$
2. Now we need to sort the columns of $M_\Phi$ and $\Phi$ by the order of eigen value, then keep the first $k$ columns of $M_\Phi$ and the same of $\Phi$, which stands for the most varied dimensions: $$\begin{align} M_{\Phi,k} & \in \Bbb{R}^{m \times k} \\ \Phi_k & \in \Bbb{R}^{n \times k} \end{align}$$
3. Then we have: $$M_k = M_{\Phi,k}\cdot\Phi_k^T, M_k \in \Bbb{R}^{m \times n} $$ , and the reconstruction with the first $k$ components is done. If we look further into it: $$\begin{align} M_k & = M_{\Phi,k}\cdot\Phi_k^T \\ & = M\cdot\Phi\Phi_k^T \\ & = U\Sigma V^T\cdot\Phi\Phi_k^T \\ & = UV^T\cdot\Sigma\Phi\Phi_k^T \\ & = UV^T\cdot\Phi\Sigma\Phi_k^T \end{align}$$ , next step might be a little tricky: thanks for the diagonal property of $\Sigma$, we can actually move the "selection" of the first $k$ components from $\Phi$ to $\Sigma$: $$\begin{align} M_k & = UV^T\cdot\Phi\ \begin{bmatrix} \Sigma_k & 0 \\ 0 & 0 \end{bmatrix}_{n\times n} \Phi^T \\ & = UV^T\cdot \begin{bmatrix} \Sigma_k & 0 \\ 0 & 0 \end{bmatrix}_{n\times n} \Phi\Phi^T \\ & = UV^T\cdot \begin{bmatrix} \Sigma_k & 0 \\ 0 & 0 \end{bmatrix}_{n\times n} \\ & = U_k\Sigma_k V_k^T \end{align}$$ , we can see this is equivalent as the SVD reconstruction.

For comparison with new image, maybe you can do like this: $$\Vert(M_k)_{:,i}-g\Vert_2$$ , but I am not sure whether there is still any option with lower complexity or not.