[Solved] AMSC808N Homework 5

Rate this product

1. Show that the Laplacian eigenmap to Rm is the solution to the following

optimization problem:min∑kij∥yi −yj∥2 subject to Y—QY =I, Y—Q1m1 =0. (1)

i,jHere, 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.