The embedding problem of
classical distance geometry is the problem of determining when a specified
nxn matrix can be realized as the
pairwise distances between n points in Euclidean
space. Constructive solutions of the embedding problem in
the 1930s inspired classical multidimensional scaling, a psychometric technique
for visualizing fallible dissimilarity data. After providing some
relevant background, I will discuss several ways in which facts about the
geometry of Euclidean distance matrices have informed recent research in
multidimensional scaling (MDS).
First, I will discuss the
problem of choosing a good initial configuration from which to begin numerical
optimization of the popular raw stress and stress criteria for metric MDS. Most
commercial algorithms use the classical solution, which can be computed
explicitly but whose interpoint distances tend to be
too small. One can do better by (1) dilating the classical solution, or by (2)
solving a simple approximation of the raw stress problem.
Second, I will discuss
extensions of classical MDS, from the case of a single fixed dissimilarity
matrix to closed convex sets of dissimilarity matrices. Important special cases
include bound constraints, which leads to new algorithms for distance matrix
completion (with applications to molecular conformation), and order constraints,
which leads to new algorithms for nonmetric MDS.
Third, I will discuss the
effect of diagonally scaling a dissimilarity matrix to a doubly stochastic
dissimilarity matrix, which operation has a beautiful relation to spherical
distance matrices.
Brief biography
Michael
Trosset received his Ph.D. in statistics from the University of
California at Berkeley. His research interests include computational
statistics, particularly the development of tractable formulations of and
efficient numerical algorithms for multidimensional scaling and related
multivariate techniques; the design and analysis of computer experiments; and
stochastic optimization. He is an associate editor of the Journal of
Computational and Graphical Statistics, and of the Journal of Multivariate
Analysis.
