Multi-Dimensional Scaling on Groups
  Leveraging the intrinsic symmetries in data for clear and efficient analysis
is an important theme in signal processing and other data-driven sciences. A
basic example of this is the ubiquity of the discrete Fourier transform which
arises from translational symmetry (i.e. time-delay/phase-shift). Particularly
important in this area is understanding how symmetries inform the algorithms
that we apply to our data. In this paper we explore the behavior of the
dimensionality reduction algorithm multi-dimensional scaling (MDS) in the
presence of symmetry. We show that understanding the properties of the
underlying symmetry group allows us to make strong statements about the output
of MDS even before applying the algorithm itself. In analogy to Fourier theory,
we show that in some cases only a handful of fundamental "frequencies"
(irreducible representations derived from the corresponding group) contribute
information for the MDS Euclidean embedding.
