3
$\begingroup$

I have some very high dimensional data, and performing Locally Linear Embedding (LLE) is very time consuming. I also have to perform several LLEs, with varying parameters, to compute the optimal number of neighbors via Spearman's Rho (a la Karbauskaite et al, see citation).

However, the data are highly linearly dependent--less than 10% of the features are necessary to preserve 98% of the variance. This does not preclude the data still being embedded in a lower dimensional manifold. Thus, my question is, is it valid to perform principal component analysis (PCA) to preserve the vast majority of the variance, followed by LLE, or will that radically change the results of the LLE? This would significantly reduce my compute time--so I'm hoping that can be done.

As an aside, the Spearman's Rho is computed based on pairwise distances--although this requires using the Geodesic distance across the manifold, NOT the Euclidean distances. Is there a way to compute Geodesic distances based on Scikit-Learn's implementation of PCA?

Citation: Karbauskaitė, Rasa, and O. Kurasova G. Dzemyda. "Selection of the number of neighbours of each data point for the locally linear embedding algorithm." Information Technology and Control 36.4 (2007): 359-364.

$\endgroup$
  • 2
    $\begingroup$ I guess LLE means local liner embedding, but generally it's a good idea to decipher all abbreviations. Also, it would be helpful to give explicit links or citations if you mention a paper ("Karbauskaite et al"). $\endgroup$ – amoeba Sep 11 '14 at 22:27
  • $\begingroup$ Thank you so much, and apologies for my poor composition! I'll add the citation. $\endgroup$ – eriophora Sep 12 '14 at 20:08
3
$\begingroup$

I am not an expert specifially on locally linear embedding, but I am sure that preprocessing with PCA would typically not affect the results of LLE (assuming that you keep enough components). Indeed, if the data are lying on a low-dimensional nonlinear manifold of dimensionality $d_1$, then this manifold can be itself contained in a linear manifold of dimensionality $d_2>d_1$ that is still smaller than the full dimensionality of that data $d_3>d_2>d_1$.

According to the book "Nonlinear Dimensionality Reduction" by Lee and Verleysen, this is a useful approach, see sections 7.2.3-7.2.4:

When data dimensionality is very high, linear dimensionality reduction by PCA may be very useful to suppress a large number of useless dimensions. [...] This also eases the work to be achieved by subsequent nonlinear methods. [...] Nonlinear methods of dimensionality reduction may take over from PCA once the dimensionality is no longer too high, between a few tens and a few hundreds, depending on the chosen method.

Your second question I don't quite understand, but there is no way to compute geodesic distances by PCA. This can be done by or after the LLE step. Preprocessing with PCA just makes sure that your linear distances do not change much after the first (linear) dimensionality reduction step. If the whole nonlinear manifold is preserved, then the geodesic distances will not change either.

$\endgroup$
  • $\begingroup$ and indeed, I wanted to compute the geodesic distance after computing the LLE. However, the function I'm using (scikit) does not expose the structure of the manifold itself, only the subsequent embedding of the points. Thus computing the geodesic distance is somewhat opaque to me. $\endgroup$ – eriophora Sep 16 '14 at 23:35
  • 1
    $\begingroup$ doing a pca with ~50 dimensions is a standard approach before applying t-SNE $\endgroup$ – gdkrmr May 25 '18 at 7:51

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.