Semidefinite embedding
Encyclopedia
Semidefinite embedding or maximum variance unfolding (MVU) is an algorithm
in computer science
, that uses semidefinite programming
to perform non-linear dimensionality reduction of high-dimensional vector
ial 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:
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.
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
in computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, that uses semidefinite programming
Semidefinite programming
Semidefinite programming is a subfield of convex optimization concerned with the optimization of a linear objective functionover the intersection of the cone of positive semidefinite matrices with an affine space, i.e., a spectrahedron....
to perform non-linear dimensionality reduction of high-dimensional vector
Coordinate vector
In linear algebra, a coordinate vector is an explicit representation of a vector in an abstract vector space as an ordered list of numbers or, equivalently, as an element of the coordinate space Fn....
ial input data.
Non-linear dimensionality reduction algorithms attempt to map high-dimensional data onto a low-dimensional Euclidean
Euclidean
Euclidean relates to Euclid , a town or others. It may refer to:Geometry...
vector space
Vector space
A vector space is a mathematical structure formed by a collection of vectors: objects that may be added together and multiplied by numbers, called scalars in this context. Scalars are often taken to be real numbers, but one may also consider vector spaces with scalar multiplication by complex...
. Maximum variance Unfolding is a member of the manifold learning family, which also include algorithms such as isomap
Isomap
In statistics, Isomap is one of several widely used low-dimensional embedding methods, where geodesic distances on a weighted graph are incorporated with the classical scaling . Isomap is used for computing a quasi-isometric, low-dimensional embedding of a set of high-dimensional data points...
and locally linear embedding. In manifold learning, the input data is assumed to be sampled from a low dimensional manifold
Manifold
In mathematics , a manifold is a topological space that on a small enough scale resembles the Euclidean space of a specific dimension, called the dimension of the 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:
- 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.
- 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.
- The low-dimensional embedding is finally obtained by application of multidimensional scalingMultidimensional scalingMultidimensional scaling is a set of related statistical techniques often used in information visualization for exploring similarities or dissimilarities in data. MDS is a special case of ordination. An MDS algorithm starts with a matrix of item–item similarities, then assigns a location to each...
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.