Description
1. In this part, you will implement a mini face recognition system. Download the ORL face database from http:
//www.cl.cam.ac.uk/Research/DTG/attarchive/pub/data/att_faces.zip. 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
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. 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. You should create an eigen-space
(using the ‘eig’ function of MATLAB) from the training set as described during the lectures without explicitly
computing the covariance matrix but instead using the L matrix as defined in class. 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 instead of ‘eig’.
Repeat the same experiment (using just the svd routine) on the Yale Face database from http://www.cse.
iitb.ac.in/~ajitvr/CS663_Fall2016/HW4/CroppedYale/. This database contains 60 images each of 38 individuals (labeled from 1 to 39, with number 14 missing). 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 20 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. [40 points]
2. Display in your report the reconstruction of any one face image from the Yale 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. [10 points]
3. 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
1
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? [10 points]
4. Given a matrix A of size m × n, write a MATLAB routine called MySVD which takes this matrix as input
and outputs the left and right singular vectors (i.e. column vectors of U and V under usual notation) and the
singular values (i.e. diagonal entries of S) of A. You are not allowed to use the svd or svds functions of MATLAB
directly. You should use only the eigenvalue decomposition routines eig or eigs for this task. Cross-check your
answer by verifying that A = USV T based on your computation. [10 points]
5. 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 kxi −x¯ −(e ·(xi −x¯))ek
2
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. [10 points]
6. Consider a matrix A of size m × n. Define P = AT A and Q = AAT
. (Note: all matrices, vectors and scalars
involved in this question are real-valued).
(a) Prove that for any vector y with appropriate number of elements, we have y
tP y ≥ 0. Similarly show
that z
tQz ≥ 0 for a vector z with appropriate number of elements. Why are the eigenvalues of P and Q
non-negative?
(b) If u is an eigenvector of P with eigenvalue λ, show that Au is an eigenvector of Q with eigenvalue λ. If v
is an eigenvector of Q with eigenvalue µ, show that AT v is an eigenvector of P with eigenvalue µ. What
will be the number of elements in u and v?
(c) If vi
is an eigenvector of Q and we define ui ,
AT vi
kAT vik2
. Then prove that there will exist some real,
non-negative γi such that Aui = γivi
.
(d) It can be shown that u
T
i uj = 0 for i 6= j and likewise v
T
i vj = 0 for i 6= j for correspondingly distinct
eigenvalues.1
. Now, define U = [v1|v2|v3|…|vm] and V = [u1|u2|u3|…|un]. Now show that A = UΓV
T
where Γ is a diagonal matrix containing the non-negative values γ1, γ2, …, γn. With this, you have just
established the existence of the singular value decomposition of any matrix A. This is a key result in linear
algebra and it is widely used in image processing, computer vision, computer graphics, statistics, machine
learning, numerical analysis, natural language processing and data mining. [5 + 5 + 5 + 5 = 20 points]
1This follows because P and Q are symmetric matrices. Consider P u1 = λ1u1 and P u2 = λ2u2. Then u
T
2 P u1 = λ1u
T
2 u1. But
u
T
2 P u1 also equal to (P
T u2)
T u1 = (P u2)
T u1 = (λ2u2)
T u1 = λ2u
T
2 u1. Hence λ2u
T
2 u1 = λ1u
T
2 u1. Since λ2 6= λ1, we must have
u
T
2 u1 = 0.
2
