Instruction: Read the homework policy.  For problems 6 and 7, include printed copies of your code with your inal homework submission.  You should submit a PDF copy of the homework and any associated codes on canvas. Your PDF must be a single ile, not multiple images.

1. Given n data points x1）x2）...）xn  lying in bd , the covariance matrix is deined as follows:

(a) Argue that Σ = XTX where X is the n by d data matrix deined as

(b) Prove that the covariance matrix is positive semi-deinite.  [大emark: A matrix A ebn 根n is positive semi-deinite if yTAy > 0 for all y e bn.]

(c) Prove that all eigenvalues of the covariance matrix are non-negative.  [Hint:  consider the quadratic form.]

(d) The covariance matrix is not necessarily positive deinite.  Let d = 4.  Describe or give an example of data for which the covariance matrix is positive semi-deinite but not positive deinite.

(e) Let d = 4.  Describe or give an example of data for which the covariance matrix is positive deinite.

[Remark: For parts (d) and (e), data point must be not trivial e.g.  (0）0）0）0)].

2. consider n data points y1）y2）...）yn  lying in bd.  The mean of the data points is deined as μ =  Σ yi. Let the points {x1  = y1  - μ) x2  = y2  - μ) ...）xn  = yn  - μ} denote the centered points i.e.  the points have zero mean  (centered at origin).  Let V be a unit vector in bd  and

let x(教)1）x(教)2）...）x(教)n  denote respectively the projection of the centered points onto the vector V.

The representation of the projections with respect to the coordinate V is c1   = (x1 )TV）c2   = (x2 )TV）...）cn  = (xn )TV.

(a) show that the variance of {c1）c2）...）cn } is given by

(b) show that the variance of {y1(T)V）y2(T)V）...）yn(T)V} is given by

(c) what is the implication of the results in (a) and (b) to inding theirst principal component of the data？ Briely interpret your result.

3.  consider n data points x1）x2）...）xn  lying in bd.  Let v1）v2   and v3   denote the irst three principal components of the data.

(a) Letx(教)i  denote the projection of a data point xi  onto the subspace spanned by theirst three principal components. what is the coordinate ofx(教)i  with respect to the basis {v1）v2）v3 }？

(b) Assume d 参 3.  what is the low dimensional embedding of the data points？

(c) Let y be a point in bd  and let y(教) be the projection of y onto the subspace spanned by the irst three principal components. prove that y(教) = VVTy where

4. Let A be an n 根 n symmetric matrix.

(a) prove that λmin (A) 三 1三i三n(min) Ai,i  i.e. the minimum eigenvalue of A is upper bounded by the the minimum value in the diagonal.

(b) prove that λmax (A) > 1三(m)i三n(ax) Ai,i  i.e. the maximum eigenvalue of A is lower bounded by the the maximum value in the diagonal.

[Hint: use Rayleigh quotient.]

5.[Bonus: 5 pts] Let A be a 2n 根 2n symmetric matrix of the following form

where the blocks A1）A2 and A3  are each n 根n matrices and A1 and A2  are symmetric matrices. prove that λmin (A) 三 min (λmin (A1 )）λmin (A2 )).  [Hint:  use Rayleigh quotient.]

6.  In this problem, we implement the principal component analysis algorithm and test it on 2-dimensional datasets.

(a) Given n points in b2 , implement an algorithm that takes the data points as input and returns the principal components.

Remark: No credit will be given to using an inbuilt pcA function. However, you can use any inbuilt function to compute eigenvalues and eigenvectors.  For example, in MATLAB, you can use the eig command.

(b) Load the data gau网网ian-noi网y available in the Hw3 folder.  compute and display the irst 2 principal components of the data.  what is the percentage of variance for the irst prin- cipal component？what is the percentage of variance for the second principal component？ summarize and explain your observations.