9
$\begingroup$

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

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

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

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 eigenvectors. If I plot the eigenvectors, e.g., top 3 of the y vectors (set the solution according to 3 eigenvalues), the results are not interpretable.

However, I can always plot the top 3 PCs and top 3 ICs, which somehow represent the original data x.

I assume the reason is because the matrix L is defined by the weighting matrix (adjcent 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)?

Thanks very much and I am looking forward to your reply.


Thanks very much for your guys replied.

My data set 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.

Please see the picture,

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 = r1*A + r2*B + r3*C$, in which r1, r2, r3 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 = b1*IC1 + b2*IC2 + b3*IC3$ (I am not sure if we can also get $M = a1*PC1 + a2*PC2 + a3*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: Columns from left to right: original signal, mixed signal, PCs, ICs, LEs

Figure 2 using 1000 nearest neighbours and sigma in the heating kernel is 0.5: Columns from left to right: original signal, mixed signal, PCs, ICs, LEs

Matlab codes with required package are uploaded to http://www.mediafire.com/?0cqr10fe63jn1d3

Thanks so much.

$\endgroup$
  • 2
    $\begingroup$ Welcome to the site! I edited your post for grammar and spelling. I also put the formula into LaTeX format. $\endgroup$ – Peter Flom Oct 10 '12 at 14:58
  • 1
    $\begingroup$ What do you mean by reduced components of x? Do you mean to say, a low-dimensional embedding of x? $\endgroup$ – hearse Oct 10 '12 at 17:31
  • $\begingroup$ This sounds interesting. Could you give a more detailed description of what, in fact, your data look like? $\endgroup$ – Placidia Oct 10 '12 at 18:06
  • $\begingroup$ Is that possible for the moderator to put my post in the 'featured post'? I really urged to get the answer. Thanks a lot. $\endgroup$ – Samo Jerom Oct 11 '12 at 10:42
3
$\begingroup$

The answer to your question is given by the mapping at the bottom of Page 6 of the original Laplacian Eigenmaps paper :

$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 this paper.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Shantanu Oct 11 '12 at 22:10
  • $\begingroup$ 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. $\endgroup$ – Shantanu Oct 11 '12 at 22:10
  • $\begingroup$ 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. $\endgroup$ – Shantanu Oct 11 '12 at 22:11
  • $\begingroup$ PS: Above, I meant "You cannot do this using LEM, at least not easily". $\endgroup$ – Shantanu Oct 11 '12 at 22:19
1
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ Everyone interested in please have a look at my question again. I put some examples. Thanks very much. $\endgroup$ – Samo Jerom Oct 11 '12 at 10:31
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.