Nonlinear Dimensionality Reduction by Locally Linear Embedding

Sam T. Roweis and Lawrence K. Saul

Introduction

Data exploration and analysis is important in many areas of science, and dimensional reduction is a big problem. How do we reduce the data dimension and preserve the relationship between data point and its neighbor at the same time?

Method

In this work, the author proposed a method called locally linear embedding (LLE). The procedure is as follows:

In the step 1, we use k nearest neighbors method to pick some neighbors. 

In the step 2, finding the weight (W) such that W*Xj is close to Xi. We can do this by minimizing the cost function

with two constrains:

(1) Wij = 0 if Xj does not belong to the set of neighbors of Xi, means we only take the k nearest neighbors into consideration.

(2) 

In the final step, we use this W to compute Y - the data been reduced. It can be done by minimizing the embedding cost function

The minimization procedure in step 2 and 3 is some standard methods in linear algebra.

Result

LLE can apply to face image or word document.