Is SDE a supervised classifier?

No. The basic method learns an embedding from geometric relationships without requiring class labels.

Does a convex program guarantee the correct manifold?

No. It gives an optimum of the specified mathematical problem under suitable solver conditions, not proof that the neighborhood assumptions match reality.

Are embedding coordinates unique?

Not generally. Rotations and reflections can preserve the Gram matrix's distances, and different modeling choices can produce different representations.

AI Glossary / Mathematics and optimization / Advanced

Semidefinite embedding

Definition

Semidefinite embedding, or SDE, is a nonlinear dimensionality-reduction method that learns a matrix of inner products while preserving specified local distances. It tries to spread the embedded points as widely as possible under those constraints, an approach also called maximum variance unfolding. A semidefinite optimization problem constructs the matrix, and an eigenvalue decomposition then supplies coordinates for the embedding.

What it means

High-dimensional observations can sometimes lie near a structure with fewer underlying degrees of freedom. SDE seeks a representation that reveals this structure without arbitrarily stretching the neighborhoods it has been told to preserve. Its use of variance differs from ordinary principal component analysis: SDE learns a new inner-product matrix subject to local geometric constraints instead of simply projecting the original coordinates onto linear directions. The quality of the result depends strongly on whether the chosen neighborhoods reflect meaningful local relationships.

How it works

Construct a neighborhood graph from the observations and specify the pairs whose squared distances must remain unchanged. In the original SDE formulation, pairs that share a neighborhood are also constrained so local angles can be preserved through distances. Let K be the unknown Gram matrix of output points. Require K to be positive semidefinite, impose centering, and enforce Kii − 2Kij + Kjj equal to each protected squared input distance. Maximize trace(K), which equals total squared distance from the origin for centered points. Recover coordinates by scaling eigenvectors by square roots of their eigenvalues. Keeping all positive eigenvalues reproduces the optimized Gram matrix; retaining fewer dimensions generally introduces additional approximation.

Three practical examples

An image-manifold experiment can investigate whether a collection varying mainly in viewing angle has a useful low-dimensional geometric representation.
A scientific-data exploration can compare local-distance preservation under SDE and a linear projection, without treating a compelling plot as proof of a physical mechanism.
A method-development study can use small synthetic manifolds to examine how neighborhood size, noise and missing connections affect the resulting embedding and computational cost.

Think of it this way

Think of straightening a bent chain while preserving the lengths of selected links. Spreading the chain can reveal a simpler shape without stretching those links. SDE uses a related unfolding intuition, but its protected relationships may include more than adjacent links. Some local configurations cannot be flattened into a chosen dimension while retaining every specified distance, and the optimization does not promise to recover a unique real-world shape.

Worked example

Take three input points A = (0, 0), B = (1, 0) and C = (0, 1), and protect all three pairwise distances. Their squared distances are AB² = 1, AC² = 1 and BC² = 2. Centering gives A′ = (−1/3, −1/3), B′ = (2/3, −1/3) and C′ = (−1/3, 2/3). Their Gram matrix is K = (1/9)[[2, −1, −1], [−1, 5, −4], [−1, −4, 5]]. Its rows sum to zero, and its eigenvalues are 1, 1/3 and 0, so it is positive semidefinite with trace 4/3. Check AB² from the matrix: 2/9 − 2(−1/9) + 5/9 = 1. Because all distances are fixed, there is no further unfolding freedom in this example. Keeping only the largest eigenvalue yields one-dimensional coordinates [0, 1/√2, −1/√2]. They preserve BC² = 2 but reduce AB² and AC² to 1/2. This shows why a truncated visualization need not retain every exact constraint satisfied by the full optimized matrix.

Illustrative case study

In a fictional project, Larch Vision explores images of a rotating manufactured part. Researchers normalize the images, inspect nearest-neighbor connections and compare embeddings under several neighborhood sizes. They check whether apparent separation corresponds to viewpoint or merely lighting changes. When a two-dimensional projection distorts protected distances, they report that truncation effect rather than claiming the solver failed its original constraints. The case describes an analytical workflow and makes no claim about classification accuracy or production performance.

Common misconceptions and mistakes

Positive semidefinite does not mean every matrix entry is positive; negative inner products are perfectly possible, as the example shows. Maximizing trace is not the same as directly minimizing rank or guaranteeing a specified output dimension. Convexity applies to the stated semidefinite program, not to every modeling choice made before it. If the neighborhood graph is disconnected, components can separate without bounded cross-component constraints, making the unconstrained variance objective problematic. Noisy data, unsuitable distances and accidental neighbor links can also undermine the intended geometry.

Business use

Use SDE when local geometric relationships are meaningful and the problem size permits the necessary optimization. Document preprocessing, distance metric, graph construction, centering and the number of retained eigenvectors. Examine constraint residuals and the eigenvalue spectrum, then quantify distortion after dimensional truncation. Compare against simpler methods on the same data. The full method requires an n-by-n matrix for n observations, so memory and solver cost can become substantial. Landmark or other approximations should be named explicitly because their computational savings come with a changed representation or approximation step.

Check your understanding

The full SDE matrix satisfies its distance constraints, but a one-dimensional plot does not. Is that necessarily a contradiction?

Answer: No. Dropping eigenvalue directions changes the Gram matrix and can distort distances, exactly as in the three-point example.

Related terms

Gram matrix
Manifold Learning
maximum variance unfolding
semidefinite programming
kernel PCA
neighborhood graph

Learn next

verify every distance in the three-point matrix and reconstruct the two-dimensional coordinates from its positive eigenvalues. Then compare full and truncated pairwise distances. On a larger synthetic example, vary neighborhood connectivity before interpreting any apparent unfolding.

Sources

Sources: Kilian Q. Weinberger, Benjamin D. Packer and Lawrence K. Saul, Nonlinear Dimensionality Reduction by Semidefinite Programming and Kernel Matrix Factorization, especially section 2, https://proceedings.mlr.press/r5/weinberger05a/weinberger05a.pdf . The centered triangle, eigenvalues and truncation calculation are original illustrations of the stated constraints, not a claimed benchmark result.

Previous: Semiconnectedness Next: Semiparametric model