# Locally-Linear Embedding Algorithm

A Locally-Linear Embedding Algorithm is a non-linear dimensionality reduction algorithm that uses an eigenvector-based optimization algorithm to find the low-dimensional embedding of points.

**AKA:**LLE.**Counter-Example(s):****See:**Sparse Matrix, Eigendecomposition_of_a_matrix, Euclidean Distance, Laplacian Eigenmap, High Dimensional Data, Data Visualization, Unsupervised Data Analysis, Nonlinear Dimensionality Reduction, Manifold Learning.

## References

### 2014

- (Wikipedia, 2014) ⇒ http://en.wikipedia.org/wiki/Nonlinear_dimensionality_reduction#Locally-linear_embedding Retrieved:2014-3-20.
- Locally-Linear Embedding (LLE)
^{[1]}was presented at approximately the same time as Isomap. It has several advantages over Isomap, including faster optimization when implemented to take advantage of sparse matrix algorithms, and better results with many problems. LLE also begins by finding a set of the nearest neighbors of each point. It then computes a set of weights for each point that best describe the point as a linear combination of its neighbors. Finally, it uses an eigenvector-based optimization technique to find the low-dimensional embedding of points, such that each point is still described with the same linear combination of its neighbors. LLE tends to handle non-uniform sample densities poorly because there is no fixed unit to prevent the weights from drifting as various regions differ in sample densities. LLE has no internal model.LLE computes the barycentric coordinates of a point

*X*_{i}based on its neighbors*X*_{j}. The original point is reconstructed by a linear combination, given by the weight matrix*W*_{ij}, of its neighbors. The reconstruction error is given by the cost function*E*(*W*).: [math] E(W) = \sum_i |{\mathbf{X}_i - \sum_j {\mathbf{W}_{ij}\mathbf{X}_j}|}^\mathsf{2} [/math]

The weights

*W*_{ij}refer to the amount of contribution the point*X*_{j}has while reconstructing the point*X*_{i}. The cost function is minimized under two constraints:(a) Each data point

*X*_{i}is reconstructed only from its neighbors, thus enforcing*W*_{ij}to be zero if point*X*_{j}is not a neighbor of the point*X*_{i}and(b) The sum of every row of the weight matrix equals 1.

: [math] \sum_j {\mathbf{W}_{ij}} = 1 [/math]

The original data points are collected in a

*D*dimensional space and the goal of the algorithm is to reduce the dimensionality to*d*such that*D*>>*d*. The same weights*W*_{ij}that reconstructs the*i*th data point in the*D*dimensional space will be used to reconstruct the same point in the lower*d*dimensional space. A neighborhood preserving map is created based on this idea. Each point X_{i}in the*D*dimensional space is mapped onto a point Y_{i}in the*d*dimensional space by minimizing the cost function: [math] C(Y) = \sum_i |{\mathbf{Y}_i - \sum_j {\mathbf{W}_{ij}\mathbf{Y}_j}|}^\mathsf{2} [/math]

In this cost function, unlike the previous one, the weights W

_{ij}are kept fixed and the minimization is done on the points Y_{i}to optimize the coordinates. This minimization problem can be solved by solving a sparse*N*X*N*eigen value problem (*N*being the number of data points), whose bottom*d*nonzero eigen vectors provide an orthogonal set of coordinates. Generally the data points are reconstructed from*K*nearest neighbors, as measured by Euclidean distance. For such an implementation the algorithm has only one free parameter*K,*which can be chosen by cross validation.

- Locally-Linear Embedding (LLE)

- ↑ S. T. Roweis and L. K. Saul, Nonlinear Dimensionality Reduction by Locally Linear Embedding, Science Vol 290, 22 December 2000, 2323–2326.

### 2010

- Lawrence K. Saul. http://cs.nyu.edu/~roweis/lle/algorithm.html
- Input X: D by N matrix consisting of N data items in D dimensions.
- Output Y: d by N matrix consisting of d < D dimensional embedding coordinates for the input points.
- 1. Find neighbours in X space [b,c].
- 2. Solve for reconstruction weights W.
- 3. Compute embedding coordinates Y using weights W.

### 2006

- (Zhang & Wang, 2006) ⇒ Zhenyue Zhang, and Jing Wang. (2006). “MLLE: modified locally linear embedding using multiple weights.” In: Proceedings of the Twentieth Annual Conference on Neural Information Processing Systems (NIPS 2006).

### 2004

- (Zhenyue, 2004) ⇒ Zhenyue Zhang. (2004). “Principal manifolds and nonlinear dimension reduction via local tangent space alignment.” In: SIAM Journal of Scientific Computing, 26.

### 2003

- (Saul & Roweis, 2003) ⇒ Lawrence K. Saul, and S. T. Roweis. (2003). “Think globally, fit locally: unsupervised learning of low dimensional manifolds.” In: Journal of Machine Learning Research, 4.
- (Donoho & Grimes, 2003) ⇒ D. Donoho, and C. Grimes. (2003). “Hessian eigenmaps: locally linear embedding techniques for high dimensional data.” In: Proceedings of the National Academy of Sciences, 10.

### 2000

- (Roweis & Saul, 2000) ⇒ Sam T. Roweis, and Lawrence K. Saul. (2000). “Nonlinear Dimensionality Reduction by Locally Linear Embedding.” In: Science Journal, 290(5500). doi:10.1126/science.290.5500.2323
- QUOTE: Many areas of science depend on exploratory data analysis and visualization. The need to analyze large amounts of multivariate data raises the fundamental problem of dimensionality reduction: how to discover compact representations of high-dimensional data. Here, we introduce locally linear embedding (LLE), an unsupervised learning algorithm that computes low-dimensional, neighborhood-preserving embeddings of high-dimensional inputs. Unlike clustering methods for local dimensionality reduction, LLE maps its inputs into a single global coordinate system of lower dimensionality, and its optimizations do not involve local minima.