## 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.)