Extreme Multidimensional Scaling

Extreme Multidimensional Scaling

Michael W. Trosset

This page is under construction! X-MDS software will be posted here as it becomes available.

Here is the Trosset-Groenen presentation from JSM 2005: Extreme Multidimensional Scaling

Here is the Trosset-Groenen proceedings paper from Interface/CSNA 2005: Multidimensional Scaling Algorithms for Large Data Sets

Here is a small (n=10) dissimilarity matrix that can be used for demonstration.

X-MDS software is a collection of Fortran 77 programs for various embedding algorithms. What you will download are text files that contain Fortran 77 source code, not executables. The source code is commented. You will need to edit the code to adapt it to your needs, e.g., to specify the number of objects to be embedded, to specify the number of dimensions desired, to specify the file from which proximity data is to be read, to specify the desired transformation of the proximities, etc. You will need a Fortran 77 compiler to compile the edited source code.

Please note that the X-MDS programs only embed, they do not display. An X-MDS program outputs the Cartesian coordinates of the embedded configuration. To display the configuration, you should use state-of-the-art visualization software.

Key Steps for Installation:

The X-MDS programs were developed in a Unix/Linux environment. If you are not working in a Unix/Linux environment, then you should create one. I created a Linux environment within the Windows XP operating system by installing Cygwin, which includes the g77 Fortran 77 compiler. Here are detailed Cygwin installation instructions.
Most of the X-MDS programs call functions from LAPACK and/or ARPACK. You should install both and create libraries to which the X-MDS programs will be linked. Here are detailed ARPACK installation instructions.
To install LAPACK, one must edit a file named make.inc. For whatever help it may be, here's the make.inc file that I used to install LAPACK in Cygwin.
Download the desired X-MDS source code.
Install your favorite software for data visualization, e.g., the GGobi Data Visualization System or CrystalVision. The latter can be obtained by anonymous ftp at ftp://ftp.galaxy.gmu.edu/pub/software/; here is a link to documentation and examples. X-MDS programs create ascii text files that are formatted to be read by CrystalVision. Please note, however, that CrystalVision is a Windows application.

Here is the X-MDS software that is currently available:

CMDS (Classical Multidimensional Scaling, aka Principal Coordinate Analysis)
The user must specify (by editing the CMDS source code) the number of objects (natoms), the name of the file that contains the natoms x natoms dissimilarity matrix, the number of dimensions in which a configuration is to be constructed (ndim), and the name of the file to which the Cartesian coordinates of the configuration will be written.
CMDS uses ARPACK to compute the ndim largest eigenvalues (and their corresponding eigenvectors) of the natoms x natoms inner product matrix. Here is the source code and here is a sample Makefile.
PCA-GMA1
PCA-GMA1 constructs an initial configuration by PCA (Principal Coordinate Analysis, aka Classical Multidimensional Scaling), then decreases the raw stress criterion (with unit weights) by peforming mgutt iterations of GMA (Guttman Majorization Algorithm). PCA-GMA1 uses ARPACK to perform PCA.
The user must specify (by editing the PCA-GMA1 source code) the number of objects (natoms), the name of the file that contains the natoms x natoms dissimilarity matrix, the number of dimensions in which a configuration is to be constructed (ndim), the number of GMA iterations (mgutt), and the name of the file to which the Cartesian coordinates of the configuration will be written.
Here is the source code and here is a sample Makefile.