[SOLVED] AMSC808N - Homework 5

Description

 Show that the Laplacian eigenmap to R^m is the solution to the following optimization problem:

min_∑k_ij∥y_i − y_j∥²₂ subject to             Y ^⊺QY = I,          Y ^⊺Q1_m×1 = 0.                     (1)

i,j

Here, y_i’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:
     • PCA;
     • Isomap;
     • LLE;
     • t-SNE;
     • 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 m: 352 data points in 3D forming a uniform grid on the manifold.

Figure 1: Scurve

• Dataset 2: Scurve generated by m and perturbed by Gaussian noise. Try various intensities, push each method to its limit.
• Dataset 3: “Emoji” dataset generated by 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