# Recovering Wasserstein Distance Matrices from Few Measurements

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 22 references that are in the map.
- First posted on arXiv 23 Sep 2025.

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

- [Computational Optimal Transport](https://mlsanity.com/paper/1803.00567/) (2018)
- [MedMNIST v2 -- A large-scale lightweight benchmark for 2D and 3D biomedical image classification](https://mlsanity.com/paper/2110.14795/) (2021)
- [Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview](https://mlsanity.com/paper/1809.09573/) (2018)
- [Manifold learning: what, how, and why](https://mlsanity.com/paper/2311.03757/) (2023)
- [Exact Reconstruction of Euclidean Distance Geometry Problem Using Low-rank Matrix Completion](https://mlsanity.com/paper/1804.04310/) (2018)
- [Wassmap: Wasserstein Isometric Mapping for Image Manifold Learning](https://mlsanity.com/paper/2204.06645/) (2022)
- [Supervised learning of sheared distributions using linearized optimal transport](https://mlsanity.com/paper/2201.10590/) (2022)
- [Matrix Completion with Cross-Concentrated Sampling: Bridging Uniform Sampling and CUR Sampling](https://mlsanity.com/paper/2208.09723/) (2022)
- [Linearized Wasserstein dimensionality reduction with approximation guarantees](https://mlsanity.com/paper/2302.07373/) (2023)
- [Matrix Coherence and the Nystrom Method](https://mlsanity.com/paper/1408.2044/) (2014)

## Abstract (arXiv)

This paper proposes two algorithms for estimating square Wasserstein distance matrices from a small number of entries. These matrices are used to compute manifold learning embeddings like multidimensional scaling (MDS) or Isomap, but contrary to Euclidean distance matrices, are extremely costly to compute. We analyze matrix completion from upper triangular samples and Nystr"om completion in which O(dlog(d)) columns of the distance matrices are computed where d is the desired embedding dimension, prove stability of MDS under Nystr"om completion, and show that it can outperform matrix completion for a fixed budget of sample distances. Finally, we show that classification of the OrganCMNIST dataset from the MedMNIST benchmark is stable on data embedded from the Nystr"om estimation of the distance matrix even when only 10% of the columns are computed.