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. You 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]
1
3. Consider a set of N vectors X = {x1,x2,…,xN} each in Rd, with average vector x¯. We have seen in class that the direction e such that is minimized, is obtained by maximizing etCe, 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 ftCf 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 gtCg. [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 with mean vector x¯. Note that each xi ∈ Rd and also x¯ ∈ Rd. 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 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 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 ATA. (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 ATA and assigns the eigenvectors of ATA (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 ATA 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.)
2