Description
1. In this part, you will implement a mini face recognition system. Download the ORL face database from the
homework folder. It contains 40 sub-folders, one for each of the 40 subjects/persons. For each person, there
are ten images in the appropriate folder named 1.pgm to 10.pgm. The images are of size 92 by 110 each.
Each
image is in the pgm format. You can view/read the images in this format, either through MATLAB or through
image viewers like IrfanView on Windows, or xv/display/gimp on Unix.
Though the face images are in different
poses, expressions and facial accessories, they are all roughly aligned (the eyes are in roughly similar locations in
all images).
For the first part of the assignment, you will work with the images of the first 32 people (numbers
from 1 to 32).
For each person, you will include the first six images in the training set (that is the first 6 images
that appear in a directory listing as produced by the dir function of MATLAB) and the remaining four images in
the testing set. Y
ou should implement the recognition system by using the eig or eigs function of MATLAB on
an appropriate data matrix. Record the recognition rate using squared difference between the eigencoefficients
while testing on all the images in the test set, for k ∈ {1, 2, 3, 5, 10, 15, 20, 30, 50, 75, 100, 150, 170}.
Plot the
rates in your report in the form of a graph. Now modify the required few lines of the code but using the svd
function of MATLAB (on the L matrix as defined in class) instead of eig or eigs.
Repeat the same experiment (using just the eig or eigs routine) on the Yale Face database from the homework folder. This database contains about 64 images each of 38 individuals (labeled from 1 to 39, with number
14 missing; some folders have slightly less than 64 images). Each image is in pgm format and has size 192 by
168.
The images are taken under different lighting conditions but in the same pose. Take the first 40 images
of every person for training and test on the remaining 24 images (that is the first 40 images that appear in
a directory listing as produced by the dir function of MATLAB).
Plot in your report the recognition rates for
k ∈ {1, 2, 3, 5, 10, 15, 20, 30, 50, 60, 65, 75, 100, 200, 300, 500, 1000} based on (a) the squared difference between all
the eigencoefficients and (b) the squared difference between all except the three eigencoefficients corresponding
to the eigenvectors with the three largest eigenvalues.
Display in your report the reconstruction of any one face
image from the ORL database using k ∈ {2, 10, 20, 50, 75, 100, 125, 150, 175} values. Plot the 25 eigenvectors
(eigenfaces) corresponding to the 25 largest eigenvalues using the subplot or subimage commands in MATLAB.
[35 points]
2. What will happen if you test your system on images of people which were not part of the training set? (i.e.
the last 8 people from the ORL database). What mechanism will you use to report the fact that there is no
matching identity? Work this out carefully and explain briefly in your report.
Write code to test whatever you
propose on all the 32 remaining images (i.e. 8 people times 4 images per person), as also the entire test set
containing 6 images each of the first 32 people. How many false positives/negatives did you get? [15 points]
3. Consider a set of N vectors X = {x1, x2, …, xN } each in R
d
, with average vector x¯. We have seen in class that
the direction e such that PN
i=1 ∥xi −x¯ −(e ·(xi −x¯))e∥
is minimized, is obtained by maximizing e
tCe, where
C is the covariance matrix of the vectors in X . This vector e is the eigenvector of matrix C with the highest
eigenvalue. Prove that the direction f perpendicular to e for which f
tCf is maximized, is the eigenvector of
C with the second highest eigenvalue. For simplicity, assume that all non-zero eigenvalues of C are distinct
and that rank(C) > 2. Extend the derivation to handle the case of a unit vector g which is perpendicular to
both e and f which maximizes g
tCg. [10 points]
4. The aim of this exercise is to help you understand the mathematics behind PCA more deeply. Do as directed:
[5+5+5+5=20 points]
(a) Prove that the covariance matrix in PCA is symmetric and positive semi-definite.
(b) Prove that the eigenvectors of a symmetric matrix are orthonormal.
(c) Consider a dataset of some N vectors in d dimensions given by {xi}
d
i=1 {xi}
N
i=1 with mean vector x¯. Note
that each xi ∈ R
d and also x¯ ∈ R
d
.
Suppose that only k eigenvalues of the corresponding covariance
matrix are large and the remaining are very small in value. Let x˜i be an approximation to xi of the form
x˜i = x¯ +
Pk
l=1 Vlαil where Vl stands for the lth eigenvector (it has d elements) and αil (it is a scalar)
stands for the lth eigencoefficient of xi. Argue why the error 1
N
PN
i=1 ∥x˜i − xi∥
2 will be small. What will
be the value of this error in terms of the eigenvalues of the covariance matrix?
(d) Consider two uncorrelated zero-mean random variables (X1, X2). Let X1 belong to a Gaussian distribution
with variance 100 and X2 belong to a Gaussian distribution with variance 1. What are the principal
components of (X1, X2)? If the variance of X1 and X2 were equal, what are the principal components?
5. The aim of this exercise is to help you understand the mathematics of SVD more deeply. Do as directed:
[5+5+10=20 points]
(a) Argue that the non-zero singular values of a matrix A are the square-roots of the eigenvalues of AAT
or
AT A. (Make arguments for both)
(b) Show that the squared Frobenius norm of a matrix is equal to the sum of squares of its singular values.
(c) A students tries to obtain the SVD of a m × n matrix A using eigendecomposition. For this, the student
computes AT A and assigns the eigenvectors of AT A (computed using the eig routine in MATLAB) to
be the matrix V consisting of the right singular vectors of A. Then the student also computes AAT
and assigns the eigenvectors of AAT
(computed using the eig routine in MATLAB) to be the matrix U
consisting of the left singular vectors of A.
Finally, the student assigns the non-negative square-roots of
the eigenvalues (computed using the eig routine in MATLAB) of either AT A or AAT
to be the diagonal
matrix S consisting of the singular values of A.
He/she tries to check his/her code and is surprised to
find that USV T
is not equal to A. Why could this be happening? What processing (s)he do to the
eigenvectors computed in order rectify this error? (Note: please try this on your own in MATLAB.)
