THE ANALYSIS OF PROXIMITY MATRICES THROUGH SUMS OF MATRICES HAVING (ANTI-)ROBINSON FORMS

A least-squares strategy is developed for representing a symmetric proximity matrix containing similarity or dissimilarity values between each pair of objects from some given set, as an approximate sum of a small number of symmetric matrices having the same size as the original but which satisfy certain simple order constraints on their entries. The primary class of constraints considered are of the Robinson (or anti-Robinson) type, where the entries in such a matrix, subject to a suitable row/column ordering, never increase (or decrease) when moving away from a main diagonal entry within any row or column. Matrices satisfying either the Robinson or anti-Robinson condition can be viewed as defining certain restricted collections of possibly overlapping subsets along with an associated measure of 'compactness' or 'salience' for each; these subsets and their compactness or salience indices form the basis for helping explain the patterning of entries in the initial proximity matrix as now reflected by the matrix sum. A number of empirical examples based on well-known published data sets are used as illustrations of how such reconstructions might be carried out and interpreted. Finally, several other types of matrix order constraints are mentioned briefly, along with a few corresponding numerical examples, to show how alternative structures also can be considered using the same type of computational strategy as in the (anti-)Robinson case.