# A Data-dependent Approach for High Dimensional (Robust) Wasserstein Alignment

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 89 references that are in the map.
- First posted on arXiv 7 Sep 2022.

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

- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [Optimal Transport for Domain Adaptation](https://mlsanity.com/paper/1507.00504/) (2015)
- [Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration](https://mlsanity.com/paper/1705.09634/) (2017)
- [Exploiting Similarities among Languages for Machine Translation](https://mlsanity.com/paper/1309.4168/) (2013)
- [Gromov-Wasserstein Alignment of Word Embedding Spaces](https://mlsanity.com/paper/1809.00013/) (2018)
- [Unsupervised Alignment of Embeddings with Wasserstein Procrustes](https://mlsanity.com/paper/1805.11222/) (2018)
- [Outlier-Robust Optimal Transport](https://mlsanity.com/paper/2012.07363/) (2020)
- [Unbalanced Optimal Transport through Non-negative Penalized Linear Regression](https://mlsanity.com/paper/2106.04145/) (2021)
- [Maximum Flow and Minimum-Cost Flow in Almost-Linear Time](https://mlsanity.com/paper/2203.00671/) (2022)
- [Randomized partition trees for exact nearest neighbor search](https://mlsanity.com/paper/1302.1948/) (2013)
- [On the universal structure of human lexical semantics](https://mlsanity.com/paper/1504.07843/) (2015)
- [Parallel Algorithms for Geometric Graph Problems](https://mlsanity.com/paper/1401.0042/) (2013)
- [Improving Approximate Optimal Transport Distances using Quantization](https://mlsanity.com/paper/2102.12731/) (2021)
- [New Streaming Algorithms for High Dimensional EMD and MST](https://mlsanity.com/paper/2111.03528/) (2021)
- [Faster Algorithms for the Geometric Transportation Problem](https://mlsanity.com/paper/1903.08263/) (2019)
- [Parallel Approximate Undirected Shortest Paths Via Low Hop Emulators](https://mlsanity.com/paper/1911.01956/) (2019)
- [Preconditioning for the Geometric Transportation Problem](https://mlsanity.com/paper/1902.08384/) (2019)
- [A near-linear time approximation scheme for geometric transportation with arbitrary supplies and spread](https://mlsanity.com/paper/1907.04426/) (2019)
- [Provably Approximated ICP](https://mlsanity.com/paper/2101.03588/) (2021)
- [Coresets for Kinematic Data: From Theorems to Real-Time Systems](https://mlsanity.com/paper/1511.09120/) (2015)
- [On Geometric Alignment in Low Doubling Dimension](https://mlsanity.com/paper/1811.07455/) (2018)
- [A Data-Dependent Algorithm for Querying Earth Mover's Distance with Low Doubling Dimensions](https://mlsanity.com/paper/2002.12354/) (2020)

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

- [Approximate Algorithms For k-Sparse Wasserstein Barycenter With Outliers](https://mlsanity.com/paper/2404.13401/) (2024)
- [On Robust Wasserstein Barycenter: The Model and Algorithm](https://mlsanity.com/paper/2312.15762/) (2023)

## Abstract (arXiv)

Many real-world problems can be formulated as the alignment between two geometric patterns. Previously, a great amount of research focus on the alignment of 2D or 3D patterns in the field of computer vision. Recently, the alignment problem in high dimensions finds several novel applications in practice. However, the research is still rather limited in the algorithmic aspect. To the best of our knowledge, most existing approaches are just simple extensions of their counterparts for 2D and 3D cases, and often suffer from the issues such as high computational complexities. In this paper, we propose an effective framework to compress the high dimensional geometric patterns. Any existing alignment method can be applied to the compressed geometric patterns and the time complexity can be significantly reduced. Our idea is inspired by the observation that high dimensional data often has a low intrinsic dimension. Our framework is a ``data-dependent'' approach that has the complexity depending on the intrinsic dimension of the input data. Our experimental results reveal that running the alignment algorithm on compressed patterns can achieve similar qualities, comparing with the results on the original patterns, but the runtimes (including the times cost for compression) are substantially lower.