# Robust Point Matching with Distance Profiles

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 60 references that are in the map.
- First posted on arXiv 19 Dec 2023.

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

- [Gromov-Wasserstein Alignment of Word Embedding Spaces](https://mlsanity.com/paper/1809.00013/) (2018)
- [Learning Generative Models across Incomparable Spaces](https://mlsanity.com/paper/1905.05461/) (2019)
- [Efficient random graph matching via degree profiles](https://mlsanity.com/paper/1811.07821/) (2018)
- [ASIF: Coupled Data Turns Unimodal Models to Multimodal Without Training](https://mlsanity.com/paper/2210.01738/) (2022)
- [A Quaternion-based Certifiably Optimal Solution to the Wahba Problem with Outliers](https://mlsanity.com/paper/1905.12536/) (2019)
- [Random Graph Matching in Geometric Models: the Case of Complete Graphs](https://mlsanity.com/paper/2202.10662/) (2022)
- [Minimax rates in permutation estimation for feature matching](https://mlsanity.com/paper/1310.4661/) (2013)
- [Strong recovery of geometric planted matchings](https://mlsanity.com/paper/2107.05567/) (2021)
- [Reversible Gromov-Monge Sampler for Simulation-Based Inference](https://mlsanity.com/paper/2109.14090/) (2021)
- [Alignment of Density Maps in Wasserstein Distance](https://mlsanity.com/paper/2305.12310/) (2023)
- [Probably certifiably correct k-means clustering](https://mlsanity.com/paper/1509.07983/) (2015)
- [AlignOT: An optimal transport based algorithm for fast 3D alignment with applications to cryogenic electron microscopy density maps](https://mlsanity.com/paper/2210.09361/) (2022)
- [Recovery guarantees for exemplar-based clustering](https://mlsanity.com/paper/1309.3256/) (2013)
- [Optimal detection of the feature matching map in presence of noise and outliers](https://mlsanity.com/paper/2106.07044/) (2021)
- [Efficiently matching random inhomogeneous graphs via degree profiles](https://mlsanity.com/paper/2310.10441/) (2023)
- [Three-Dimensional Alignment of Density Maps in Cryo-Electron Microscopy](https://mlsanity.com/paper/2206.08027/) (2022)
- [Matching Map Recovery with an Unknown Number of Outliers](https://mlsanity.com/paper/2210.13354/) (2022)

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

- [Cluster-Aware Matching via Laplacian Optimal Transport](https://mlsanity.com/paper/2607.16178/) (2026)

## Abstract (arXiv)

Computational difficulty of quadratic matching and the Gromov-Wasserstein distance has led to various approximation and relaxation schemes. One of such methods, relying on the notion of distance profiles, has been widely used in practice, but its theoretical understanding is limited. By delving into the statistical complexity of the previously proposed method based on distance profiles, we show that it suffers from the curse of dimensionality unless we make certain assumptions on the underlying metric measure spaces. Building on this insight, we propose and analyze a modified matching procedure that can be used to robustly match points under a certain probabilistic setting. We demonstrate the performance of the proposed methods using simulations and real data applications to complement the theoretical findings. As a result, we contribute to the literature by providing theoretical underpinnings of the matching procedures based on distance invariants like distance profiles, which have been widely used in practice but rarely analyzed theoretically.