# Minimax rates in permutation estimation for feature matching

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Oct 2013.

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

- [Random initialisations performing above chance and how to find them](https://mlsanity.com/paper/2209.07509/) (2022)
- [Random Graph Matching in Geometric Models: the Case of Complete Graphs](https://mlsanity.com/paper/2202.10662/) (2022)
- [Optimal Full Ranking from Pairwise Comparisons](https://mlsanity.com/paper/2101.08421/) (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)
- [Permuted and Unlinked Monotone Regression in ℝd: an approach based on mixture modeling and optimal transport](https://mlsanity.com/paper/2201.03528/) (2022)
- [Matrix Reordering for Noisy Disordered Matrices: Optimality and Computationally Efficient Algorithms](https://mlsanity.com/paper/2201.06438/) (2022)
- [Shuffled linear regression through graduated convex relaxation](https://mlsanity.com/paper/2209.15608/) (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)
- [Statistical Inference for Optimal Transport Maps: Recent Advances and Perspectives](https://mlsanity.com/paper/2506.19025/) (2025)
- [Statistical-computational gap in multiple Gaussian graph alignment](https://mlsanity.com/paper/2512.00610/) (2025)

## Abstract (arXiv)

The problem of matching two sets of features appears in various tasks of computer vision and can be often formalized as a problem of permutation estimation. We address this problem from a statistical point of view and provide a theoretical analysis of the accuracy of several natural estimators. To this end, the minimax rate of separation is investigated and its expression is obtained as a function of the sample size, noise level and dimension. We consider the cases of homoscedastic and heteroscedastic noise and establish, in each case, tight upper bounds on the separation distance of several estimators. These upper bounds are shown to be unimprovable both in the homoscedastic and heteroscedastic settings. Interestingly, these bounds demonstrate that a phase transition occurs when the dimension d of the features is of the order of the logarithm of the number of features n. For d=O(log n), the rate is dimension free and equals σ (log n)1/2, where σ is the noise level. In contrast, when d is larger than clog n for some constant c>0, the minimax rate increases with d and is of the order σ(dlog n)1/4. We also discuss the computational aspects of the estimators and provide empirical evidence of their consistency on synthetic data. Finally, we show that our results extend to more general matching criteria.