Semidefinite Embedding - Optimization Formulation

Optimization Formulation

Let be the original input and be the embedding. If are two neighbors, then the local isometry constraint that needs to be satisfied is:

Let be the Gram matrices of and (i.e.: ). We can express the above constraint for every neighbor points in term of :

In addition, we also want to constraint the embedding to center at the origin:

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:

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 prevents the objective function from going to infinity. Proof:

Let where if i and j are neighbors and otherwise.

Since the graph has N points, the distance between any two points . We can then bound the objective function as follow:

The objective function can be rewritten purely in the form of the Gram matrix:

Finally, the optimization can be formulated as:

Maximize

Subject to and where

After the Gram matrix is learned by semidefinite programming, the output can be obtained via Cholesky decomposition. In particular, the Gram matrix can be written as where is the i-th element of eigenvector of the eigenvalue .

It follows that the -th element of the output is .