2. (adapted from Boyd 4.1). We saw in class that the k-means algorithm relies on two observations: (1) that the best assignment with fixed representative vectors is to assign every data vector to the cluster with the nearest representative and (2) that the best choice for representative vectors given a fixed cluster assignment is to choose the mean vector for each cluster. Here, are are going to prove the second point, which we did not show in class. To do this, we will deal with minimizing our clustering objective for a single cluster, with representative vector z, and assigned vectors x1,x2,x3,,xL. We want to show that the optimal choice is z=x, where x=(1/L)(x1+x2++xL) is a vector that is the mean of all vectors in the cluster. (a) For a vector xi, show that xiz2=(xix)(zx)2 (b) We can define the clustering objective for just this cluster as Jclust=i=1Lxiz2. We can mimimize each cluster separately for this step of the k-means algorithm, so we want to choose z to minimize this. Show that: Jclust=i=1Lxiz2=[i=1Lxix22(xix)T(zx)]+Lzx2 Hints: Use your answer from part (a), recall that uv=uTv, and pay careful attention to what does and does not depend on the index of summation, i. (c) Show that i=1L(xix)T(zx)=[i=1L(xix)T](zx)=0 Hints: Pay attention to the term in brackets, remember the definition of x, and remember that the transpose is linear, so (u+v)T=uT+vT (d) Combine b and c to show that Jclust=i=1Lxix2+Lzx2. The vector z only shows up in one place in this problem. We want to find z to minimize Jclust. Explain why this happens when z=x