Provide credit to any sources other than the course sta that helped you solve the problems.
This includes all students you talked to regarding the problems.
You can look up de nitions/basics online (e.g., wikipedia, stack-exchange, etc)
Suppose W is a k
d matrix, where each entry of W is picked inde-
Problem 1. (10 points).1
1
pendently from the set f
p
;
p
g. In other words, for each i; j,
k
k
2:
Pr
Wij =
pk
= Pr
Wij = pk
=
1
1
1
2 R
Let x
d. If we pick W with this distribution, show that
1. !
E k
!
k2
!k
k2
W x
2
= x
2:
2. Just like the Gaussian matrix we considered in the class, we might as well take a random matrix W designed like this for JL transform. What is an advantage of this matrix over the Gaussian matrix?
Problem 2. (10 points). Suppose d = 1. Come up with a set of n real numbers, and an initial set of k distinct cluster centers such that the k-means algorithm does not converge to the best
solution of the k-means clustering problem. You can choose any value of n, and k that you want!
(Hint: small n, k are easier to think about.)
Problem 3. (15 points). Let C = x1 xjCj1
be a cluster where xi 2 Rd. Let
X
cav =
xi
C xi
jCj
2
Prove that for any c 2 Rd,
X
X
kxi
ck22kxi cavk22
xi2C
xi2C
(Hint: xi c = xi cav + cav c)
Problem 4. (30 points). Please see attached jupyter notebook.
1
