Semidefinite embedding

From Wikipedia, the free encyclopedia

 This article or section contains too much jargon and may need simplification or further explanation.
Please discuss this issue on the talk page, and/or remove or explain jargon terms used in the article. Editing help is available.
This article has been tagged since June 2007.
This article or section needs to be wikified to meet Wikipedia's quality standards.
Please help improve this article with relevant internal links. (June 2007)

In computer science, semidefinite embedding (SDE) or maximum variance unfolding (MVU) is an algorithm in that uses semidefinite programming to perform non-linear dimensionality reduction of high-dimensional vectorial input data.

Non-linear dimensionality reduction algorithms attempt to map high-dimensional data onto a low-dimensional Euclidean vector space. Maximum Variance Unfolding is a member of the manifold learning family, which also include algorithms such as isomap and locally linear embedding. In manifold learning, the input data is assumed to be sampled from a low dimensional manifold that is embedded inside of a higher dimensional vector space. The main intuition behind MVU is to exploit the local linearity of manifolds and create a mapping that preserves local neighborhoods at every point of the underlying manifold.

MVU creates a mapping from the high dimensional input vectors to some low dimensional Euclidean vector space in the following three steps:

  1. A neighborhood graph is created. Each input is connected with its k-nearest input vectors (according to Euclidean distance metric) and all k-nearest neighbors are connected with each other. If the data is sampled well enough, the resulting graph is a discrete approximation of the underlying manifold.
  2. The neighborhood graph is "unfolded" with the help of semidefinite programming. Instead of learning the output vectors directly, the semidefinite programming aims to find an inner product matrix that maximizes the pairwise distances between any two inputs that are not connected in the neighborhood graph.
  3. The low-dimensional embedding is finally obtained by application of multidimensional scaling on the learned inner product matrix.

The steps of applying semidefinite programming followed by a linear dimensionality reduction step to recover a low-dimensional embedding into a Euclidean space were first proposed by Linial, London, and Rabinovich in a now classical article (see below).

[edit] See also

[edit] External links