Eigenfaces

Eigenfaces are super interesting extensions to the concept of eigenvectors, and also serve as fascinating visualizations. Basically, if you have a large dataset of face images, eigenfaces are a set of face-like images that collectively capture the variation in the original set of faces. Given a subset of the eigenfaces, an original face can be encoded as relative amounts of each eigenface, and then rebuilt by adding the encoded amounts of each eigenface together.

Let’s explore these in more detail!

The Dataset

Say you have a large dataset of faces and wish to find these eigenfaces. We’ll use a cropped version of the Labeled Faces in the Wild (LFW) dataset that will contain 5000 example faces, each 32px by 32px (1024 pixels total per face), and saved in the grayscale format. Let’s visualize the first 100 faces:

Original Faces

As stated above, each image has pixels, and can be stored as a vector . For the images in our dataset, we can store all of the images in a matrix ; one row for each image vector .

Vector Spaces

In our dataset, the images lie in a 1024-dimensional vector space, which can be considered fairly high-dimensional. However, since images of faces share many characteristics, the images are likely to be clustered together in the 1024-dimensional space. Therefore, it would seem plausible that a lower dimensional vector subspace could still accurately represent the images, while preserving most of the variability in the original data.

The goal then becomes finding the -dimensional subspace in which the data approximately lies.

In order to do this, we will start by finding a direction that will form a 1-dimensional subspace that approximates the data with the most variability possible. Concretely, if we have an -dimensional vector , we can project an -dimensional image onto it by , resulting in a 1-dimensional, scalar value. The variability of the set of projected images can then be calculated as . For our matrix of images, the projections can be written as , and the variance written more concisely as the squared norm of the projections, .

As stated above, we want to find a direction that preserves the most variance. Thus we want to maximize the projection variance , subject to being unit-length () since we only want a direction. If we rewrite the equation in a certain way, we can discover some clever math:

Notice that in the final line, a large matrix multiplied by the vector becomes equal to a scalar variance multiplied by the same vector. That equality leads us to the concept of eigenvectors & eigenvalues, which will help us to maximize these equations w.r.t. the variance.

Eigenvectors & Eigenvalues

An eigenvector is a vector that when multiplied by a matrix , becomes equal to itself multiplied by a scalar eigenvalue .

Notice the correlation between this definition and the rewritten equation from above. Let’s write them out again:

From this we can see that our matrix maps to the matrix (and is known as the covariance matrix of ), is the eigenvector , and the variance is the eigenvalue . So, with a bit of clever rewriting, we were able to redefine our goal in terms of eigenvectors/eigenvalues, which can be computed using existing algorithms.

Goal, continued

With our problem redefined, we can now compute the vector onto which to approximate the data with the most variability by solving for the eigenvectors & eigenvalues of the covariance matrix, . If we assume that the eigenvectors have length 1 (we assumed ), then we can basically assume there will be one eigenvector per eigenvalue (technically both and will still be valid eigenvectors with the same eigenvalue, but that’s okay). Now we have a matrix consisting of the eigenvectors, and a matrix consisting of the associated eigenvalues.

So, if we solved for the eigenvectors and eigenvalues, the that maximizes the projection variance will be the eigenvector with the largest associated eigenvalue.

K-dimensional subspace

Now that we know how to find a vector that creates a 1-dimensional subspace to project the data into with the most variance, finding vectors to create a -dimensional subspace with the most variance possible is trivial. Simply select the top eigenvectors with the highest associated eigenvalues.

PCA

The algorithm we have discussed so far is known as Principal Component Analysis, or PCA. It allows for determining the prinicipal components (the eigenvectors) that capture the most variance in the original data when projecting into the subspace created by them. The idea of PCA is that it allows for an -dimensional dataset to be represented in a reduced set of -dimensions, and thus is also known as a dimensionality reduction algorithm.

Eigenfaces

It is now time to discuss eigenfaces. As discussed above, the eigenvectors can be considered the principal components of a dataset, and each capture a certain amount of the variability within the original data.

As we also mentioned above, if each image is -dimensional ( pixels), then each eigenvector will also be -dimensional. Each value is computed to capture the most variation at the th pixel location across the dataset.

Therefore, if we visualize each as if it were an image, we will find that they appear as ghost-like faces. Let’s plot the top 36 eigenfaces for our dataset:

Eigenfaces

Fascinating!

Projection & Rebuilding

Now that we have the eigenfaces, we can project our original faces onto a subset of of them, thus reducing each image from -dimensions down to a vector of -dimensions.

The images can then be rebuilt in dimensions from the encodings, with some loss in accuracy, using the following:

Let’s project our data onto eigenfaces, and then rebuild the original faces using the eigenfaces and encodings for each image, resulting in the images below:

Recovered Faces

If we compare them side by side, we should see that the rebuilt images were close to the originals:

Faces Comparison

So, while each original image had 1024 pixels, by using only 100 eigenface encodings for each image, we were able to rebuild each image with pretty good accuracy. Awesome!

Final thoughts

Overall, eigenfaces are super interesting. Hopefully this post serves as an interesting guide to them, and sparks interest into further exploration on the topic, in which case one should start with the original paper, by Turk & Pentland!

Update – 01.25.15

I’ve added demo code written in the Octave/Matlab language to go along with this post. It will compute the eigenfaces of the face dataset and produce the visualizations as shown. Check it out on github!