Intrinsic dimensionality detection criterion based on Locally Linear Embedding

Lian Meng, Piotr Breitkopf


We revisit in this work the Locally Linear Embedding (LLE) algorithm which is a widely employed technique in dimensionality reduction. With a particular interest on the correspondences of nearest neighbors in the original and em- bedded spaces, we observe that, when prescribing low-dimensional embedding spaces, LLE remains merely a weight preserving, rather than a neighborhood preserving algorithm. We propose thus a ”neighborhood preserving ratio” crite- rion to estimate a minimal intrinsic dimensionality required for neighbourhood preservation. We validate its efficiency on a set of synthetic data, including S-curve, swiss roll, as well as a dataset of grayscale images.

Full Text:



Balasubramanian M., Schwartz E.L.: The isomap algorithm and topological sta- bility. In: Science, vol. 295(5552), pp. 7–7, 2002.

Cox T., Cox M.: Multidimensional Scaling. In: Chapman&Hall, London, UK, 1994.

Jolliffe I.: Principal component analysis. Wiley Online Library, 2002.

Polito M., Perona P.: Grouping and dimensionality reduction by locally linear

embedding. In: , 2002.

Saul L.K., Roweis S.T.: An introduction to locally linear embedding. In: unpub-

lished. Available at: http://www. cs. toronto. edu/ ̃ roweis/lle/publications. html,

Saul L.K., Roweis S.T.: Think globally, fit locally: unsupervised learning of low

dimensional manifolds. In: The Journal of Machine Learning Research, vol. 4, pp.

–155, 2003.

Saul L.K., Weinberger K.Q., Ham J.H., Sha F., Lee D.D.: Spectral methods for

dimensionality reduction. In: Semisupervised learning, pp. 293–308, 2006.



  • There are currently no refbacks.