Multi-Dimensional Scaling on Groups
This work addresses the problem of improving efficiency and interpretability in data analysis for researchers in signal processing and related fields, but it appears incremental as it extends existing symmetry concepts to MDS.
The paper investigates how symmetry groups affect multi-dimensional scaling (MDS) for dimensionality reduction, showing that group properties allow predicting MDS outputs and that only a few irreducible representations contribute to embeddings in some cases.
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.