Fitting new images from a SVD/PCA calculation

Question

I'm trying to replicate the ideas from the Eigenface page on wikipedia. From a hundred sample images represented by a data matrix $\bf X$ (where each image flattened to a vector of length $n$, thus $\bf X$ is a $100$ by $n$ matrix), I've computed a SVD decomposition:

\begin{equation} \bf X = U \Sigma V^{T} \end{equation}

hence:

\begin{equation} \bf X X^{T} = U \Sigma^2 U^{T} \end{equation}

By taking a subset of the largest $q$ eigenmodes, I can approximate the matrix (let $\sigma_1 \ge \sigma_2 \ge \cdots$):

\begin{equation} {\bf X} \approx \sigma_1 u_1 v_1^{T} + \sigma_2 u_2 v_2^{T} + \cdots + \sigma_q u_q v_q^{T} \end{equation}

Now given a new vector $y$, which represents an image not in $\bf X$, how do I determine the weighting of the $q$ eigenvectors $\bf U$ to best represent my new image $y$? Except for pathological cases, is this representation unique?

In short, what I'd like to do is this (from the wiki page):

These eigenfaces can now be used to represent both existing and new faces: we can project a new (mean-subtracted) image on the eigenfaces and thereby record how that new face differs from the mean face.

How do I do that projection?

Answer 1

The "projection" that is referred to is a vector projection. To calculate the projection of vector $\mathbf{a}$ onto vector $\mathbf{b}$, you use the inner product of the two vectors:

$$ \mathbf{a_{proj}} = \langle \mathbf{a}, \mathbf{b} \rangle \mathbf{b} $$

$\mathbf{a_{proj}}$ in this case is the vector component of $\mathbf{a}$ that lies in the same direction of $\mathbf{b}$. In Euclidean space, the inner product operator is defined as their dot product:

$$ \langle \mathbf{a}, \mathbf{b} \rangle = \mathbf{a} \cdot \mathbf{b} = \sum_{i=1}^{n}a_ib_i $$

where $n$ is the number of components in the vectors $\mathbf{a}$ and $\mathbf{b}$ and $a_i$ and $b_i$ are the $i$-th component of vectors $\mathbf{a}$ and $\mathbf{b}$, respectively. Intuitively, by calculating the inner product of the two vectors, you find "how much of" vector $\mathbf{a}$ goes in the direction of vector $\mathbf{b}$. Note that this is a signed quantity, so a negative value would mean that the angle between the two vectors is greater than 90 degrees, as illustrated by an alternative definition for the projection operator:

$$ \mathbf{a_{proj}} = |\mathbf{a}| \cos(\theta) \mathbf{b} $$

where $\theta$ is the angle between the two vectors.

So, given a vector $\mathbf{a}$ and a bunch of basis vectors $\mathbf{b_i}$, one can find "how much of $\mathbf{a}$" goes in each of the directions of each of the basis vectors. Typically, those basis vectors will all be mutually orthogonal. In your case, the SVD is an orthogonal decomposition, so this condition should be satisfied. So, to accomplish what you describe, you would take the matrix of eigenvectors $\mathbf{U}$ and calculate the inner product of the candidate vector $\mathbf{y}$ with each of the matrix's columns:

$$ p_i = \mathbf{y} \cdot \mathbf{u_i} $$

The scalar value $p_i$ that you get from each inner product represents how well the vector $\mathbf{y}$ "lined up" with the $i$-th eigenvector. Since the eigenvectors are orthonormal, you could then reconstruct the original vector $\mathbf{y}$ as follows:

$$ \mathbf{y} = \sum_{i=1}^n p_i \mathbf{u_i} $$

You asked whether this representation is unique; I'm not sure exactly what you mean, but it is not unique in the sense that a given vector $\mathbf{y}$ could be decomposed by projection onto any number of orthonormal bases. The eigenvectors contained in the matrix $\mathbf{U}$ are one such example, but you could use any number of others. For instance, calculating the discrete Fourier transform of $\mathbf{y}$ can be viewed as projecting it onto an orthonormal basis of complex exponential vectors of varying frequency.