# Matching Map Recovery with an Unknown Number of Outliers

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 60 references that are in the map.
- First posted on arXiv 24 Oct 2022.

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

- [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)
- [Maximum Flow and Minimum-Cost Flow in Almost-Linear Time](https://mlsanity.com/paper/2203.00671/) (2022)
- [Random Graph Matching in Geometric Models: the Case of Complete Graphs](https://mlsanity.com/paper/2202.10662/) (2022)
- [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)
- [Strong recovery of geometric planted matchings](https://mlsanity.com/paper/2107.05567/) (2021)
- [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)
- [Localization in 1D non-parametric latent space models from pairwise affinities](https://mlsanity.com/paper/2108.03098/) (2021)
- [Optimal detection of the feature matching map in presence of noise and outliers](https://mlsanity.com/paper/2106.07044/) (2021)
- [One-Way Matching of Datasets with Low Rank Signals](https://mlsanity.com/paper/2204.13858/) (2022)
- [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)
- [Matrix Reordering for Noisy Disordered Matrices: Optimality and Computationally Efficient Algorithms](https://mlsanity.com/paper/2201.06438/) (2022)

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

- [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 noisy feature-vectors. The distinctive feature of our setting is that we do not assume that all the vectors of the first set have their corresponding vector in the second set. If n and m are the sizes of these two sets, we assume that the matching map that should be recovered is defined on a subset of unknown cardinality k^*≤ min(n,m). We show that, in the high-dimensional setting, if the signal-to-noise ratio is larger than 5(dlog(4nm/α))1/4, then the true matching map can be recovered with probability 1-α. Interestingly, this threshold does not depend on k^* and is the same as the one obtained in prior work in the case of k = min(n,m). The procedure for which the aforementioned property is proved is obtained by a data-driven selection among candidate mappings hatπk:k∈[min(n,m)]. Each hatπk minimizes the sum of squares of distances between two sets of size k. The resulting optimization problem can be formulated as a minimum-cost flow problem, and thus solved efficiently. Finally, we report the 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 algorithms studied in this work.