Maximum Variance Unfolding (MVU), also known as Semidefinite Embedding (SDE), is an algorithm in computer science that uses semidefinite programming to perform non-linear dimensionality reduction of high-dimensional vectorial input data.

It is motivated by the observation that kernel Principal Component Analysis (kPCA) does not reduce the data dimensionality, as it leverages the Kernel trick to non-linearly map the original data into an inner-product space.

MVU creates a mapping from the high dimensional input vectors to some low dimensional Euclidean vector space in the following 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.

Let ${\displaystyle X\,\!}$ be the original input and ${\displaystyle Y\,\!}$ be the embedding. If ${\displaystyle i,j\,\!}$ are two neighbors, then the local isometry constraint that needs to be satisfied is:

Let ${\displaystyle G,K\,\!}$ be the Gram matrices of ${\displaystyle X\,\!}$ and ${\displaystyle Y\,\!}$ (i.e.: ${\displaystyle G_{ij}=X_{i}\cdot X_{j},K_{ij}=Y_{i}\cdot Y_{j}\,\!}$). We can express the above constraint for every neighbor points ${\displaystyle i,j\,\!}$ in term of ${\displaystyle G,K\,\!}$:

In addition, we also want to constrain the embedding ${\displaystyle Y\,\!}$ to center at the origin:

${\displaystyle 0=|\sum _{i}Y_{i}|^{2}\Leftrightarrow (\sum _{i}Y_{i})\cdot (\sum _{i}Y_{i})\Leftrightarrow \sum _{i,j}Y_{i}\cdot Y_{j}\Leftrightarrow \sum _{i,j}K_{ij}}$