Locally Linear Embedding LLE

The simple intuition behind LLE is that each input point, x , and its fe-nearest neighbours are locally linear, that is, they lie on or near a linear patch of the manifold. By making this assumption the local geometry can be characterised by linear reconstruction weights, W, that reconstruct each point x from its A -nearest neighbours. The weights are measured by the squared distance cost function 

2-dimensional embeddings of the S-Curve dataset found by Locally Linear Embedding with k = S 

Although similar methods existed before LLE to model the local geometry of a manifold (e.g. Local PCA [13]), the novel feature of LLE is that it maps the local geometric models into a single, coherent, coordinate system. As well as this, by modelling the local geometry in terms of reconstruction coefficients, the core methodology of LLE can be used to embed new data points into a previously learnt manifold, a problem which is described in more detail in Chap. 5. 

---

Unlike the global approaches previously described. Locally Linear Embedding (LLE) is a local approach and as described in Sect. 2.3.4 the x feature matrix is sparse. This sparse feature matrix is beneficial as it lowers the computational cost of the eigendecomposition. Specifically, the computational cost of eigendecomposition for a sparse nxn matrix, F, is 0 rn ) when using specific sparse analysis methods [8]. Here, r is the ratio of nonzero elements in F to the total number of elements n. 

Saul, L.K., Rowels, S. An introduction to locally linear embedding. URL http //www.es. toronto.edu/ roweis/lle/publications.html... 

Another variant of LLE that aims to better handle noise is Neighbourhood Smoothing Embedding (NSE) [36]. NSE is a noise reducing variant of LLE that utilises local linear surface estimators [37] to obtain a more accurate representation of the local... 

---