Editing Semidefinite embedding (section)

== Algorithm ==
MVU creates a mapping from the high dimensional input vectors to some low dimensional [[Euclidean vector]] space in the following steps:<ref>{{Harvnb|Weinberger, Sha and Saul|2004a|loc=page 7.}}</ref>

# A [[neighbourhood (topology)|neighbourhood]] 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 neighbourhood 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 neighbourhood graph while preserving the nearest neighbors distances. 
# 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 [[Nathan Linial|Linial]], London, and Rabinovich.<ref>{{harvnb|Linial, London and Rabinovich|1995}}</ref>