A model and algorithm for multidimensional scaling with external constraints on the distances

Abstract

A method for externally constraining certain distances in multidimensional scaling configurations is introduced and illustrated. The approach defines an objective function which is a linear composite of the loss function of the point configuration X relative to the proximity data P and the loss of X relative to a pseudo-data matrix R . The matrix R is set up such that the side constraints to be imposed on X 's distances are expressed by the relations among R 's numerical elements. One then uses a double-phase procedure with relative penalties on the loss components to generate a constrained solution X . Various possibilities for constructing actual MDS algorithms are conceivable: the major classes are defined by the specification of metric or nonmetric loss for data and/or constraints, and by the various possibilities for partitioning the matrices P and R . Further generalizations are introduced by substituting R by a set of R matrices, R i , i =1, ... r , which opens the way for formulating overlapping constraints as, e.g., in patterns that are both row- and column-conditional at the same time.