Avoiding unwanted results in locally linear embedding: A new understanding of regularization
This addresses a subtle but important problem in dimensionality reduction for researchers using LLE, though it is incremental as it clarifies an existing method rather than introducing a new one.
The paper identifies that locally linear embedding (LLE) can produce unwanted results, such as 'projection patterns', even when regularization is not expected to be needed, and demonstrates through mathematical proof and numerical examples that regularization effectively prevents these issues.
We demonstrate that locally linear embedding (LLE) inherently admits some unwanted results when no regularization is used, even for cases in which regularization is not supposed to be needed in the original algorithm. The existence of one special type of result, which we call ``projection pattern'', is mathematically proved in the situation that an exact local linear relation is achieved in each neighborhood of the data. These special patterns as well as some other bizarre results that may occur in more general situations are shown by numerical examples on the Swiss roll with a hole embedded in a high dimensional space. It is observed that all these bad results can be effectively prevented by using regularization.