Recovering Wasserstein Distance Matrices from Few Measurements
By: Muhammad Rana , Abiy Tasissa , HanQin Cai and more
Potential Business Impact:
Helps computers learn from less data.
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\"{o}m completion in which $\mathcal{O}(d\log(d))$ columns of the distance matrices are computed where $d$ is the desired embedding dimension, prove stability of MDS under Nystr\"{o}m 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\"{o}m estimation of the distance matrix even when only 10\% of the columns are computed.
Similar Papers
Provable Non-Convex Euclidean Distance Matrix Completion: Geometry, Reconstruction, and Robustness
Optimization and Control
Finds object shapes from partial distance clues.
Slicing the Gaussian Mixture Wasserstein Distance
Machine Learning (CS)
Makes computer models of data faster and better.
Quantization-based Bounds on the Wasserstein Metric
Machine Learning (CS)
Makes computer math faster for pictures.