Geometric multidimensional scaling: efficient approach for data dimensionality reduction

Abstract

Multidimensional scaling (MDS) is an often-used method to reduce the dimensionality of multidimensional data nonlinearly and to present the data visually. MDS minimizes some stress function which variables are coordinates of points in the projected lower-dimensional space. Recently, the so-called Geometric MDS has been developed, where the stress function and multidimensional scaling, in general, are considered from the geometric point of view. Using ideas of Geometric MDS, it is possible to construct the iterative procedure of minimization of the stress where coordinates of a separate point of the projected space are moved to the new position defined analytically. In this paper, we discover and prove the main advantage of Geometric MDS theoretically: changing the position of all the points of the projected space simultaneously (independently of each other) in the directions and with steps, defined analytically by Geometric MDS strategy for a separate point, decreases the MDS stress. Moreover, the analytical updating of coordinates of projected points in each iteration has a simple geometric interpretation. New properties of Geometric MDS have been discovered. The obtained results allow us for the future development of a class of new both sequential and parallel algorithms. Ideas for global optimization of the stress are highlighted.