Minimum Volume Embedding

Blake Shaw, Tony JebaraAISTATS 2007

Abstract

Minimum Volume Embedding (MVE) is a non-linear dimensionality reduction technique that improves upon Semidefinite Embedding (SDE) by explicitly "flattening" the data manifold. While SDE focuses on unfolding manifolds by maximizing total variance, it often spreads information across unnecessary dimensions. MVE addresses this by maximizing variance in the target low dimensions while simultaneously minimizing it in all others. This approach produces 2D and 3D visualizations that capture significantly more of the data's "energy" and local structure, as demonstrated across synthetic, image, and social network datasets.

Introduction: The Challenge of High-Dimensional Visualization

In machine learning, high-dimensional data—such as images, social network profiles, or biological sequences—often resides on a much simpler, low-dimensional "manifold." Visualizing this data requires "unfolding" the manifold into a 2D or 3D space.

A popular method, Semidefinite Embedding (SDE), achieves this by maximizing the total variance of the data while preserving local distances. However, SDE has a significant drawback: it pulls the data apart in every possible direction. This often "puffs out" the manifold into higher dimensions, spreading the important information (eigenvalue energy) across a long tail. When this data is eventually truncated for visualization, much of the local distance information is lost.

Methods: From Unfolding to Flattening

MVE modifies the SDE framework by introducing an objective function that explicitly flattens the embedding. Instead of maximizing total variance, MVE aims to:

  1. Maximize the variance in the first $d$ target dimensions.
  2. Minimize the variance in the remaining $D-d$ dimensions.

The resulting cost function—the sum of "tail" eigenvalues minus the sum of "top" eigenvalues—is concave. To solve this, the authors derive a variational upper bound and propose an iterative alternating minimization algorithm. The process alternates between a standard eigendecomposition to find eigenvectors and Semidefinite Programming (SDP) to optimize the kernel matrix. This approach typically converges within 10 iterations, ensuring a monotonic decrease in the cost function.

Key Insights: The Importance of the Eigengap

A core contribution of MVE is the recognition that a good embedding must be "flat" as well as "unfolded." By driving energy away from higher dimensions, MVE creates a much larger "eigengap"—the difference between the last preserved eigenvalue and the first discarded one. This gap ensures the 2D "shadow" of the data is more accurate and less sensitive to noise.

Figure 2: MVE successfully collapses the "Hub and Spokes" model into its intrinsic 2D shape, capturing 100% of the variance in the first two dimensions.

This effect is particularly visible in "hub-and-spoke" structures common in social networks. While SDE might turn a 2D star shape into an N-dimensional sphere, MVE successfully collapses it back into its intrinsic 2D form.

Experimental Results

The authors evaluated MVE against SDE and Kernel PCA (KPCA) on several datasets, including the Frey Face dataset and USPS handwritten digits.

Figure 4: Comparison of KPCA, SDE, and MVE on USPS digits (top) and Frey faces (bottom). Pie charts indicate the percentage of variance captured in the top dimensions; MVE consistently captures more "energy" in the primary dimensions.

Key findings include:

  • Social Networks: MVE captured 77.5% of the eigenvalue energy in 2D, significantly higher than SDE (41.7%) and KPCA (29.3%).
  • Image Datasets: On faces and digits, MVE captured 10-15% more variance than SDE, leading to cleaner visualizations where local distances were more faithfully preserved.
  • Phylogenetic Trees: MVE provided the most legible visualizations of species relationships for salamanders and crustaceans, preventing the "collapsing" effect often seen in sparse biological datasets.

Conclusion and Limitations

While MVE provides superior visualizations, it comes with a higher computational cost. The iterative nature of the algorithm makes it roughly 10 times slower than SDE. Like other SDP-based methods, it scales at $O(N^3)$, limiting its direct application to very large datasets without approximation techniques like "Landmark" SDE. Future work focuses on developing specialized solvers to improve efficiency and exploring global optimization guarantees.

Summary updated

BibTeX
@article{shaw2007minimum,
  author = {Blake Shaw and Tony Jebara},
  title = {{Minimum Volume Embedding}},
  journal = {AISTATS},
  year = {2007},
}
Figure