1. (5 pts) Show that the Laplacian eigenmap to Rm is the solution to the following optimization problem:
min∑kij∥yi − yj∥22 subject to Y ⊺QY = I, Y ⊺Q1m×1 = 0. (1)
i,j
Here, yi’s are columns of Y , and Y is m × m, and the rest of notation as in Section 7.3 of 4-DimReduction.pdf.
2. (20 pts) The goal of this problem is to practice and compare various methods for dimensional reduction.
• Methods:
(a) PCA;
(b) Isomap;
(c) LLE;
(d) t-SNE;
(e) Diffusion map.
Diffusion map should be programmed from scratch. Readily available codes can be used for the rest. For example, the built-in Matlab function can be used for tSNE; S. Roweis’s code can be used for LLE; my code for isomap is in the lecture notes. If you use some standard code, specify its source, read its description, and be ready to adjust parameters in it.
• Dataset 1: Scurve generated by MakeScurveData.m: 352 data points in 3D forming a uniform grid on the manifold.
Figure 1: Scurve
• Dataset 2: Scurve generated by MakeScurveData.m and perturbed by Gaussian noise. Try various intensities, push each method to its limit.
• Dataset 3: “Emoji” dataset generated by MakeEmojiData.m: a set of 1024 images each one is 40 × 40 pixels. Images vary from a smiley face to an angry face and in the degree of blurring. Its subsampled set is shown in Fig. 2. Note
1
that picking a good value of for the diffusion map might require some effort as the distances between the nearest neighbors are very nonuniform. You should be able to get a nice 2D surface embedded into 3D with a right . Using α = 0 or α = 1 is up to you.
