A general nonmetric technique for finding the smallest coordinate space for a configuration of points

LetA₁,A₂, ...,A_n be anyn objects, such as variables, categories, people, social groups, ideas, physical objects, or any other. The empirical data to be analyzed are coefficients of similarity or distance within pairs (A_i,A_i), such as correlation coefficients, conditional probabilities or likelihoods, psychological choice or confusion, etc. It is desired to represent these data parsimoniously in a coordinate space, by calculatingm coordinates {x_ia} for eachA_i for a semi-metricd of preassigned formd_ij =d(|x_i1 -x_j1|, |x_i2 -x_j2|, ..., |x_im -x_jm|). The dimensionalitym is sought to be as small as possible, yet satisfy the monotonicity condition thatd_ij <d_kl whenever the observed data indicate thatA_i is closer toA_j thanA_k is toA_l. Minkowski and Euclidean spaces are special metric examples ofd. A general coefficient of monotonicity is defined, whose maximization is equivalent to optimal satisfaction of the monotonicity condition, and which allows various options both for treatment of ties and for weighting error-of-fit. A general rationale for algorithm construction is derived for maximizing by gradient-guided iterations; this provides a unified mathematical solution to the basic operational problems of norming the gradient to assure proper convergence, of trading between speed and robustness against undesired stationary values, and of a rational first approximation. Distinction is made between single-phase (quadratic) and two-phase (bilinear) strategies for algorithm construction, and between hard-squeeze and soft-squeeze tactics within these strategies. Special reference is made to the rank-image and related transformational principles, as executed by current Guttman-Lingoes families of computer programs.This research was supported in part by the National Science Foundation of the United States Government, through Grant No. GS 929 to the University of Michigan.I am deeply indebted for many helpful comments on earlier drafts of this paper received from Joseph Kruskal, James Lingoes, and the managing editor.