16
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Future readers might find this implementation valuable. $\endgroup$ – Emre May 2 '12 at 20:26
11
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Great answer thanks! For "unique", I meant unique in the sense of the basis given by the SVD. I'm guessing that given an orthonormal basis, then the $\bf y$ you compute must be unique - but if the basis is not orthonormal then it may not be (since if they weren't orthogonal, then we could find a smaller basis set)? $\endgroup$ – Hooked May 1 '12 at 15:39
  • $\begingroup$ Still not sure what you're getting at. $\mathbf{y}$ is the vector that you've distilled your new image down to, so it's only as unique as the original image and the process that you use to determine the corresponding vector. A vector space basis by definition consists of linearly-independent vectors, which forces the property of mutual orthogonality. You do note correctly that if you projected $\mathbf{y}$ onto a set of nonorthogonal vectors, you could possibly come up with a more compact representation if the space spanned by the vectors had lesser underlying dimensionality (a smaller basis). $\endgroup$ – Jason R May 2 '12 at 1:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.