Minimum Volume Embedding
Based on the paper (please cite it if you use this code):
Blake Shaw and Tony Jebara, "Minimum Volume Embedding"
in Proceedings of the Eleventh International Conference on
Artificial Intelligence and Statistics, San Juan, Puerto Rico, 2007.
Minimum Volume Embedding (MVE) is an algorithm for non-linear dimensionality reduction that uses semidefinite programming (SDP) and matrix factorization to find a low-dimensional embedding that preserves local distances between points while representing the dataset in many fewer dimensions. MVE follows an approach similar to algorithms such as Semidefinite Embedding (SDE), in that it learns a kernel matrix using an SDP before applying Kernel Principal Component Analysis (KPCA). However, the objective function for MVE directly optimizes the eigenspectrum of the data to preserve as much of its energy as possible within the few dimensions available to the embedding. Simultaneously, remaining eigenspectrum energy is minimized in directions orthogonal to the embedding thereby keeping data in a so-called minimum volume manifold. We show how MVE improves upon SDE in terms of the volume of the preserved embedding and the resulting eigenspectrum, producing better visualizations for a variety of synthetic and real-world datasets, including simple toy examples, face images, handwritten digits, phylogenetic trees, and social networks.
Installation notes:
Download and Install a SDP solver
- download CSDP
- edit the csdp.m file so that the dos and system calls point to the full path of the csdp executable e.g. info=system([csdp '
fname '.dat-s' ' 'fname '.sol']); becomes info=system(['/Users/blake/bin/matlab/csdp 'fname '.dat-s' ' ' fname '.sol']);
Download and install MVE
- downlad and unzip a copy of MVE
- edit the file setuppath.m to add the directory containing csdp to matlabs path
- in matlab run mvedriver for an example of how to use mve
To use MVE-full
- note: MVE requires the YALMIP package
- download a copy of YALMIP (http://control.ee.ethz.ch/~joloef/wiki/pmwiki.php?n=Main.Download)
- edit the file setuppath.m so that YALMIP is in your path, and yalmip can access CSDP
MVE version 0.4 code as a .zip file is here.
MVE version 0.5 code as a .zip file is here.
Copyright: Blake Shaw and Tony Jebara, Columbia University, 2006.