Letting symmetry guide visualization: multidimensional scaling on groups
share
Multidimensional scaling (MDS) is a fundamental tool for both data visualization and dimensionality reduction. Given a finite collection of points and distances between them, MDS finds a map of these points into Euclidean space which optimally preserves distances. Once in Euclidean space, it is often easier to both visualize and apply standard data analytics and machine learning algorithms. Crucially, MDS automatically provides a measure of how well distances are preserved as a function of the dimension of the target space. In this paper we show that when MDS is applied to a set of points on which a group G acts and the metric defining distance is invariant with respect to the action of the group, then MDS can be understood (and its output calculated) in terms of the representation theory of G. In particular when our set of points is G itself, this means that the MDS embedding can be calculated using the Fourier transform on groups. We propose this as an alternative implementation of MDS. We investigate an example in which we apply MDS to permutations from the symmetric group and where distances between permutations are calculated by either the Hamming distance, Cayley distance, or Coxeter distance.
READ FULL TEXT