# PCA, ICA and Laplacian eigenmaps

## Question

I am very interested in the Laplacian Eigenmaps method. Currently, I am using it to do dimension reduction on my medical data sets.

However, I have run into a problem using the method.

For example, I have some data (spectra signals), and I can use PCA (or ICA) to get some PCs (or ICs). The problem is how to get similar dimension reduced components of the original data using LE?

According to the Laplacian eigenmaps method, we need to solve the generalised eigenvalue problem, which is

$$L y = \lambda D y$$

Here $$y$$ is the eigenvector. If I plot the e.g. top 3 eigenvectors (the solution according to 3 eigenvalues), the results are not interpretable.

However, when I plot the top 3 PCs and top 3 ICs, the results always seem to clearly (visually) represent the original data $$x$$.

I assume the reason is because the matrix $$L$$ is defined by the weight matrix (Adjacency matrix $$W$$), and the data $$x$$ has been fitted with the heat kernel to create $$W$$, which is using an exponential function. My question is how to retrieve the reduced components of $$x$$ (not the eigenvector $$y$$ of matrix $$L$$)?

## Data

My dataset is restricted and not easy to demonstrate the problem. Here I created a toy problem to show what I meant and what I want to ask.

Firstly, I create some sine waves A, B, C showing in red curves (first column of the figure). A, B, and C have 1000 samples, in other words, saved in 1x1000 vectors.

Secondly, I mixed the sources A, B, C using randomly created linear combinations, e.g., $$M = r_1*A + r_2*B + r_3*C$$, in which $$r_1, r_2, r_3$$ are random values. The mixed signal $$M$$ is in very high dimensional space, e.g., $$M \in R^{1517\times1000}$$, 1517 is randomly chosen high dimensional space. I show only first three rows of signal M in green curves (second column of the figure).

Next, I run PCA, ICA and Laplacian eigenmaps to get the dimension reduction results. I chose to use 3 PCs, 3 ICs, and 3 LEs to do a fair comparison (blue curves showed as 3rd, 4th, and last column of the figure respectively).

From the results of PCA and ICA (3rd, 4th column of the figure), we can see that we can interpret the results as some dimension reduction, i.e., for ICA results, we can recover the mixed signal by $$M = b_1*IC1 + b_2*IC2 + b_3*IC3$$ (I am not sure if we can also get $$M = a_1*PC1 + a_2*PC2 + a_3*PC3$$ with PCA results but the result seems quite right for me).

However, please look at the results of LE, I can barely interpret the results (last column of the figure). It seems something 'wrong' with the reduced components. Also, I want to mention that eventually the plot of the last column is the eigenvector $$y$$ in formula $$L y = \lambda D y$$

Have you people got more ideas?

Figure 1 using 12 nearest neighbours and sigma in the heating kernel is 0.5:

Figure 2 using 1000 nearest neighbours and sigma in the heating kernel is 0.5:

Sourcecode: Matlab code with required package

• What do you mean by reduced components of x? Do you mean to say, a low-dimensional embedding of x? Oct 10, 2012 at 17:31
• This sounds interesting. Could you give a more detailed description of what, in fact, your data look like? Oct 10, 2012 at 18:06

The answer to your question is given by the mapping at the bottom of Page 6 of the original Laplacian Eigenmaps paper (Belkin & Niyogi, 2003):

$$x_i \rightarrow (f_1(i), \dots, f_m(i))$$

So for instance, the embedding of a point $$x_5$$ in, say, the top 2 "components" is given by $$(f_1(5), f_2(5))$$ where $$f_1$$ and $$f_2$$ are the eigenvectors corresponding to the two smallest non-zero eigenvalues from the generalized eigenvalue problem $$L f = \lambda D f$$.

Note that unlike in PCA, it is not straightforward to obtain an out-of-sample embedding. In other words, you can obtain the embedding of a point that was already considered when computing $$L$$, but not (easily) if it is a new point. If you're interested in doing the latter, look up Out-of-Sample Extensions for LLE, Isomap, MDS, Eigenmaps, and Spectral Clustering (Bengio et al., 2003).

• I am a little confused about what you are considering as your variables. From what I understand, your matrix $M$ consists of 1517 samples from a 1000-dimensional space. When you do PCA (or ICA) on this matrix, you are able to recover the underlying modes of variation pretty well: for instance, in column 3 in your figures, row 1,2,3 correspond to the bases C, A, B respectively. This makes sense. However, in your code, when you perform LEM, you call the function on $M^T$ (mixedSignal'), which is not consistent with the above. Oct 11, 2012 at 22:10
• So, first, in the matrix $M$, what are you variables and what are your observations? Second, from your analysis it appears that are you are not just looking for the embedding of $M$ using LEM, but also the equivalent of the eigenvectors as in PCA, right? You cannot do this LEM, at least not easily. Read this paper to understand why. Oct 11, 2012 at 22:10
• If all that you are looking for is the embedding, then that is easily given by the mapping $x_i \rightarrow (f_1(i), \dots, f_m(i))$. Look up my answer for details. In your code, change line 47 and use mixedSignal instead of its transpose; the result mappedX will then give you the 3-dimensional embedding of your 1517 points. Oct 11, 2012 at 22:11
• PS: Above, I meant "You cannot do this using LEM, at least not easily". Oct 11, 2012 at 22:19
• I wonder if it's worth mentioning UMAP as a modern alternative to LEM specifically designed to allow out-of-sample embeddings. The reference implementation of UMAP actually uses LEM for initialization by default. Mar 27, 2021 at 17:22

Here is the link to Prof Trosset's Web page of the course and also he is writing a book http://mypage.iu.edu/~mtrosset/Courses/675/notes.pdf which gets updated every week or so. Also the R functions for Laplacian eigen maps are given. Just try it for yourself. You may also consider this paper by Belkin

Thanks Abhik Student of Prof Trosset

Unlike PCA- Laplacian eigenmaps uses the generalized eigen vectors corresponding to the smallest eigenvalues. It skips the eigen vector with the smallest eigen value (could be zero), and uses the eigen vectors corresponding to the next few smallest eigen values. PCA is a maximum variance preserving embedding using the kernel/gram matrix. Laplacian Eigenmaps is posed more as a minimization problem with respect to the combinatorial graph laplacian (refer papers by Trosset).

• Everyone interested in please have a look at my question again. I put some examples. Thanks very much. Oct 11, 2012 at 10:31