Semidefinite embedding
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. Algorithm. 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. Optimization formulation. Let formula_1 be the original input and formula_2 be the embedding. If formula_3 are two neighbors, then the local isometry constraint that needs to be satisfied is: Let formula_5 be the Gram matrices of formula_6 and formula_7 (i.e.: formula_8). We can express the above constraint for every neighbor points formula_3 in term of formula_5: In addition, we also want to constrain the embedding formula_7 to center at the origin: formula_13 As described above, except the  distances of neighbor points are preserved, the algorithm aims to maximize the pairwise distance of every pair of points. The objective function to be maximized is: formula_14 Intuitively, maximizing the function above is equivalent to pulling the points as far away from each other as possible and therefore "unfold" the manifold. The local isometry constraint Let formula_15 where formula_16 prevents the objective function from diverging (going to infinity). Since the graph has N points, the distance between any two points formula_17. We can then bound the objective function as follows: The objective function can be rewritten purely in the form  of the Gram matrix: Finally, the optimization can be formulated as: formula_20 After the Gram matrix formula_21 is learned by semidefinite programming, the output formula_22 can be obtained via Cholesky decomposition. In particular, the Gram matrix can be written as formula_23 where formula_24 is the i-th element of eigenvector formula_25 of the eigenvalue formula_26. It follows that the formula_27-th element of the output formula_28 is formula_29.