  Dimension reduction algorithms are a crucial part of many data science
pipelines, including data exploration, feature creation and selection, and
denoising. Despite their wide utilization, many non-linear dimension reduction
algorithms are poorly understood from a theoretical perspective. In this work
we consider a generalized version of multidimensional scaling, which is posed
as an optimization problem in which a mapping from a high-dimensional feature
space to a lower-dimensional embedding space seeks to preserve either inner
products or norms of the distribution in feature space, and which encompasses
many commonly used dimension reduction algorithms. We analytically investigate
the variational properties of this problem, leading to the following insights:
1) Solutions found using standard particle descent methods may lead to
non-deterministic embeddings, 2) A relaxed or probabilistic formulation of the
problem admits solutions with easily interpretable necessary conditions, 3) The
globally optimal solutions to the relaxed problem actually must give a
deterministic embedding. This progression of results mirrors the classical
development of optimal transportation, and in a case relating to the
Gromov-Wasserstein distance actually gives explicit insight into the structure
of the optimal embeddings, which are parametrically determined and
discontinuous. Finally, we illustrate that a standard computational
implementation of this task does not learn deterministic embeddings, which
means that it learns sub-optimal mappings, and that the embeddings learned in
that context have highly misleading clustering structure, underscoring the
delicate nature of solving this problem computationally.
