# Optimal detection of the feature matching map in presence of noise and outliers

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 50 references that are in the map.
- First posted on arXiv 13 Jun 2021.

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

- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [Image Matching across Wide Baselines: From Paper to Practice](https://mlsanity.com/paper/2003.01587/) (2020)
- [D3Feat: Joint Learning of Dense Detection and Description of 3D Local Features](https://mlsanity.com/paper/2003.03164/) (2020)
- [D2D: Keypoint Extraction with Describe to Detect Approach](https://mlsanity.com/paper/2005.13605/) (2020)
- [Iterative Algorithm for Discrete Structure Recovery](https://mlsanity.com/paper/1911.01018/) (2019)
- [Linear Regression with Sparsely Permuted Data](https://mlsanity.com/paper/1710.06030/) (2017)
- [Minimax Rates and Efficient Algorithms for Noisy Sorting](https://mlsanity.com/paper/1710.10388/) (2017)
- [Minimax rates in permutation estimation for feature matching](https://mlsanity.com/paper/1310.4661/) (2013)
- [A Permutation-based Model for Crowd Labeling: Optimal Estimation and Robustness](https://mlsanity.com/paper/1606.09632/) (2016)
- [Isotonic regression with unknown permutations: Statistics, computation, and adaptation](https://mlsanity.com/paper/2009.02609/) (2020)
- [Optimal Rates of Statistical Seriation](https://mlsanity.com/paper/1607.02435/) (2016)
- [Optimal Permutation Recovery in Permuted Monotone Matrix Model](https://mlsanity.com/paper/1911.10604/) (2019)
- [Minimax Testing of Identity to a Reference Ergodic Markov Chain](https://mlsanity.com/paper/1902.00080/) (2019)
- [Towards Optimal Estimation of Bivariate Isotonic Matrices with Unknown Permutations](https://mlsanity.com/paper/1806.09544/) (2018)
- [Minimax Lower Bounds for Linear Independence Testing](https://mlsanity.com/paper/1601.06259/) (2016)

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

- [One-Way Matching of Datasets with Low Rank Signals](https://mlsanity.com/paper/2204.13858/) (2022)
- [Matrix Reordering for Noisy Disordered Matrices: Optimality and Computationally Efficient Algorithms](https://mlsanity.com/paper/2201.06438/) (2022)
- [Matching Map Recovery with an Unknown Number of Outliers](https://mlsanity.com/paper/2210.13354/) (2022)
- [Covariance alignment: from maximum likelihood estimation to Gromov-Wasserstein](https://mlsanity.com/paper/2311.13595/) (2023)
- [Robust Point Matching with Distance Profiles](https://mlsanity.com/paper/2312.12641/) (2023)

## Abstract (arXiv)

We consider the problem of finding the matching map between two sets of d dimensional vectors from noisy observations, where the second set contains outliers. The matching map is then an injection, which can be consistently estimated only if the vectors of the second set are well separated. The main result shows that, in the high-dimensional setting, a detection region of unknown injection can be characterized by the sets of vectors for which the inlier-inlier distance is of order at least d1/4 and the inlier-outlier distance is of order at least d1/2. These rates are achieved using the estimated matching minimizing the sum of logarithms of distances between matched pairs of points. We also prove lower bounds establishing optimality of these rates. Finally, we report results of numerical experiments on both synthetic and real world data that illustrate our theoretical results and provide further insight into the properties of the estimators studied in this work.