15.2 Double centering. In this problem we will prove the correctness of the double centering step in Isomap when working with Euclidean distances. Dene X and

x as in exercise 15.1, and dene X as the centered version of X, that is, let xi

= xi ???? x be the ith column of X. Let K = X>X, and let D denote the Euclidean distance matrix, i.e., Dij = kxi ???? xjk.

(a) Show that Kij = 1 2 (Kii +Kjj + D2 ij ).

(b) Show that K = X>X = K???? 1 mK11> ???? 1 m11>K+ 1 m2 11>K11>.

(c) Using the results from

(a) and

(b) show that Kij = ????

1 2



D2 ij ????

1 m

Xm k=1 D2 ik ????

1 m

Xm k=1 D2 kj + D



;

where D = 1 m2 P u P v D2 u;v is the mean of the m2 entries in D.

(d) Show that K = ????1 2HDH, where H = Im ???? 1 m11>.