# On Probabilistic Embeddings in Optimal Dimension Reduction

arXiv: https://arxiv.org/abs/2408.02433 · HTML: https://mlsanity.com/paper/2408.02433/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 48 references that are in the map.
- First posted on arXiv 5 Aug 2024.

## Builds on (most cited first, 13 of 13)

- [UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction](https://mlsanity.com/paper/1802.03426/) (2018)
- [Sliced Gromov-Wasserstein](https://mlsanity.com/paper/1905.10124/) (2019)
- [Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and Costs](https://mlsanity.com/paper/2106.01128/) (2021)
- [Multi-marginal optimal transport: theory and applications](https://mlsanity.com/paper/1406.0026/) (2014)
- [Semi-relaxed Gromov-Wasserstein divergence with applications on graphs](https://mlsanity.com/paper/2110.02753/) (2021)
- [On the existence of Monge maps for the Gromov-Wasserstein problem](https://mlsanity.com/paper/2210.11945/) (2022)
- [A contribution to Optimal Transport on incomparable spaces](https://mlsanity.com/paper/2011.04447/) (2020)
- [Generalized Dimension Reduction Using Semi-Relaxed Gromov-Wasserstein Distance](https://mlsanity.com/paper/2405.15959/) (2024)
- [Distributional Reduction: Unifying Dimensionality Reduction and Clustering with Gromov-Wasserstein](https://mlsanity.com/paper/2402.02239/) (2024)
- [On Assignment Problems Related to Gromov-Wasserstein Distances on the Real Line](https://mlsanity.com/paper/2205.09006/) (2022)
- [The Gromov-Wasserstein distance between spheres](https://mlsanity.com/paper/2306.10586/) (2023)
- [Central Limit Theorems for Classical Multidimensional Scaling](https://mlsanity.com/paper/1804.00631/) (2018)
- [Variational problems involving unequal dimensional optimal transport](https://mlsanity.com/paper/1904.00939/) (2019)

## Built on by (most cited first, 5 of 5)

- [Geometry-Preserving Encoder/Decoder in Latent Generative Models](https://mlsanity.com/paper/2501.09876/) (2025)
- [Large data limits and scaling laws for tSNE](https://mlsanity.com/paper/2410.13063/) (2024)
- [On sparsity, extremal structure, and monotonicity properties of Wasserstein and Gromov-Wasserstein optimal transport plans](https://mlsanity.com/paper/2602.16265/) (2026)
- [Network Learning with Semi-relaxed Gromov-Wasserstein](https://mlsanity.com/paper/2606.02223/) (2026)
- [On the Abundance of Critical Points of the t-SNE Energy](https://mlsanity.com/paper/2609.04379/) (2026)

## Abstract (arXiv)

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.