[Solved] MATH5473 Homework 1-PCA and MDS

1. PCA experiments: Take any digit data ( 0,,9), or all of them, from website http://www-stat.stanford.edu/~tibs/ElemStatLearn/datasets/zip.digits/ and perform PCA experiments with Matlab or other languages (e.g. ipynb) you are familiar:
   • Set up data matrix X = (x₁,,x_n) R^pn;
   • Compute the sample mean _n and form X = X e^T_n;
   • Compute top k SVD of X = US_kV ^T;
   • Plot eigenvalue curve, i.e. i _i(_n)/tr(_n) (i = 1,,k), with top-k eigenvalue _i for sample covariance matrix , which gives you explained variation of data by principal components;
   • Use imshow to visualize the mean and top-k principle components as left singular vectors U = [u₁,,u_k];
   • For k = 1, order the images (x_i) (i = 1,,n) according to the top first right singular vector, v₁, in an ascending order of v₁(i);
   • For k = 2, scatter plot (v₁,v₂) and select a grid on such a plane to show those images on the grid (e.g. Figure 14.23 in book [ESL]: Elements of Statistical Learning).
   • * You may try the parallel analysis with permutation test to see how many significantprinciple components you will obtain.
2. MDS of cities: Go to the following website http://www.geobytes.com/citydistancetool.htm Perform the following experiment.
   • Input a few cities (no less than 7) in your favorite, and collect the pairwise air traveling distances shown on the website in to a matrix D;
   • Make your own codes of Multidimensional Scaling algorithm for D;
   • Plot the normalized eigenvalues _i/(^P_{i i}) in a descending order of magnitudes, analyze your observations (did you see any negative eigenvalues? if yes, why?);

1

Homework 1. PCA and MDS 2

• Make a scatter plot of those cities using top 2 or 3 eigenvectors, and analyze yourobservations.

3. Positive Semi-definiteness: Recall that a n-by-n real symmetric matrix K is called positive semi-definite (s.d. or 0) iff for every x Rⁿ, x^TKx 0.
   • Show that 0 if and only if its eigenvalues are all nonnegative.
   • Show that d_ij = K_ii+K_jj 2K_ij is a squared distance function, e. there exists vectors u_i,v_j Rⁿ (1 i,j n) such that d_ij = ku_i u_jk².
   • Let Rⁿ be a signed measure s.t. ^P_{i i} = 1 (or e^T = 1) and H = I e^T be the Householder centering matrix. Show that 0 for matrix D = [d_ij].
   • If 0 and), show that 0 (elementwise sum), and 0 (Hadamard product or elementwise product).
4. Distance: Suppose that d : R^p R^p R is a distance function.
   • Is d² a distance function? Prove or give a counter example.

• Is d a distance function? Prove or give a counter example.

5. Singular Value Decomposition: The goal of this exercise is to refresh your memory about the singular value decomposition and matrix norms. A good reference to the singular value decomposition is Chapter 2 in this book:

Matrix Computations, Golub and Van Loan, 3rd edition.

• Existence: Prove the existence of the singular value decomposition. That is, show that if A is an mn real valued matrix, then A = UV ^T, where U is mm orthogonal matrix, V is nn orthogonal matrix, and = diag(₁,₂,,_p) (where p = min{m,n}) is an mn diagonal matrix. It is customary to order the singular values in decreasing order: _{1 2 p} 0. Determine to what extent the SVD is unique. (See Theorem 2.5.2, page 70 in Golub and Van Loan).
• Best rank-k approximation operator norm: Prove that the best rank-k approximation of a matrix in the operator norm sense is given by its SVD. That is, if A = UV ^T is the SVD of A, then A_k = U_kV ^T (where _k = diag(₁,₂,,_k,0,,0) is a diagonal matrix containing the largest k singular values) is a rank-k matrix that satisfies

kA A_kk = min kA Bk.

rank(B)=k

(Recall that the operator norm of A is kAk = max_kxk=1 kAxk. See Theorem 2.5.3 (page 72) in Golub and Van Loan).

• Best rank-k approximation Frobenius norm: Show that the SVD also provides the best rank-k approximation for the Frobenius norm, that is, A_k = U_kV ^T satisfies

kA A_kk_F = min kA Bk_F.

rank(B)=k

Homework 1. PCA and MDS 3

• Schatten p-norms: A matrix norm k k that satisfies

kQAZk = kAk,

for all Q and Z orthogonal matrices is called a unitarily invariant norm. The Schatten p-norm of a matrix A is given by the `_p norm (p 1) of its vector of singular values, namely,

.

Show that the Schatten p-norm is unitarily invariant. Note that the case p = 1 is sometimes called the nuclear norm of the matrix, the case p = 2 is the Frobenius norm, and p = is the operator norm.

• Best rank-k approximation for unitarily invariant norms: Show that the SVD provides the best rank-k approximation for any unitarily invariant norm. See also 7.4.51 and

7.4.52 in:

Matrix Analysis, Horn and Johnson, Cambridge University Press, 1985.

• Closest rotation: Given a square n n matrix A whose SVD is A = UV ^T, show that its closest (in the Frobenius norm) orthogonal matrix R (satisfying RR^T = R^TR = I) is given by R = UV ^T. That is, show that

,

where A = UV ^T. In other words, R is obtained from the SVD of A by dropping the diagonal matrix . Use this observation to conclude what is the optimal rotation that aligns two sets of points p₁,p₂,,p_n and q₁,,q_n in R^d, that is, find R that minimizes . See also (the papers are posted on course website):

• [Arun87] Arun, K. S., Huang, T. S., and Blostein, S. D., Least-squares fitting of two 3-D point sets, IEEE Transactions on Pattern Analysis and Machine Intelligence, 9 (5), pp. 698700, 1987.
• [Keller75] Keller, J. B., Closest Unitary, Orthogonal and Hermitian Operators to a Given Operator, Mathematics Magazine, 48 (4), pp. 192197, 1975.
• [FanHoffman55] Fan, K. and Hoffman, A. J., Some Metric Inequalities in the Space of Matrices, Proceedings of the American Mathematical Society, 6 (1), pp. 111116, 1955.