Understanding Machine Learning: From Theory to Algorithms

340 Dimensionality Reduction

if an eigenvalue decomposition of some matrixCis required, verify that this

decomposition can be computed.

4.An Interpretation of PCA as Variance Maximization:

Letx 1 ,...,xmbemvectors inRd, and letxbe a random vector distributed

according to the uniform distribution overx 1 ,...,xm. Assume thatE[x] = 0.

1. Consider the problem of finding a unit vector,w∈Rd, such that the
   random variable〈w,x〉has maximal variance. That is, we would like to
   solve the problem

argmax

w:‖w‖=1

Var[〈w,x〉] = argmax

w:‖w‖=1

1

m

∑m

i=1

(〈w,xi〉)^2.

Show that the solution of the problem is to setwto be the first principle

vector ofx 1 ,...,xm.

2. Letw 1 be the first principal component as in the previous question. Now,
   suppose we would like to find a second unit vector,w 2 ∈Rd, that maxi-
   mizes the variance of〈w 2 ,x〉, but is also uncorrelated to〈w 1 ,x〉. That is,
   we would like to solve:

argmax

w:‖w‖=1,E[(〈w 1 ,x〉)(〈w,x〉)]=0

Var[〈w,x〉].

Show that the solution to this problem is to setwto be the second principal

component ofx 1 ,...,xm.

Hint:Note that

E[(〈w 1 ,x〉)(〈w,x〉)] =w> 1 E[xx>]w=mw> 1 Aw,

whereA =

∑

ixix

>i. Sincewis an eigenvector ofAwe have that the

constraintE[(〈w 1 ,x〉)(〈w,x〉)] = 0 is equivalent to the constraint

〈w 1 ,w〉= 0.

5.The Relation between SVD and PCA: Use the SVD theorem (Corol-

lary C.6) for providing an alternative proof of Theorem 23.2.

6.Random Projections Preserve Inner Products:The Johnson-Lindenstrauss

lemma tells us that a random projection preserves distances between a finite

set of vectors. In this exercise you need to prove that if the set of vectors are

within the unit ball, then not only are the distances between any two vectors

preserved, but the inner product is also preserved.

LetQbe a finite set of vectors inRdand assume that for everyx∈Qwe

have‖x‖≤1.

1. Letδ∈(0,1) and n be an integer such that

=

√

6 log(|Q|^2 /δ)

n ≤^3.

Prove that with probability of at least 1−δover a choice of a random