1. Show that the Laplacian eigenmap to Rm is the solution to the following
optimization problem:
min∑kij∥yi −yj∥2 subject to YQY =I, YQ1m1 =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 t- SNE; 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.
Figure 2: The subsampled “Emoji” dataset.
• Submit a report on the performance of these methods on each dataset. Include all necessary figures.
2
