Semidefinite embedding
From Wikipedia, the free encyclopedia
Similar to locally linear embedding and Isomap, Semidefinite embedding (SDE) is an algorithm to perform non-linear dimensionality reduction.
These algorithms attempt to map high dimensional, data that is sampled from a lower dimensional underlying manifold, onto a low dimensional euclidean vector space. The main intuition is to exploit the local linearity of manifolds and create a mapping that preserves local neighborhoods at every point of the underlying manifold.
Semidefinite Embedding (or Maximum Variance Unfolding, how it is also often referred to) 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). Also, 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 to the learned inner product matrix.
[edit] External links
- [http://www.seas.upenn.edu/~kilianw/Downloads/MVU.html MVU Matlab code online
- [http://www.springerlink.com/content/t21q747q278qx4x1/?p=fbd7b5250ef0498ba460ce125a4b8f0f&pi=0 International Journal of Computer Vision. In Special Issue: Computer Vision and Pattern Recognition-CVPR 2004 Guest Editor(s): Aaron Bobick, Rama Chellappa, Larry Davis, Pages 77-90, Volume 70, Number 1, Springer Netherlands
