Minimax rates in permutation estimation for feature matching

MaRDI QIDQ2810764zbMATH OpenFDO

Authors Arnak S. Dalalyan, Olivier Collier

Publication date 6 June 2016

Published in Journal of Machine Learning Research (JMLR) (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1310.4661, http://jmlr.csail.mit.edu/papers/v17/collier16a.html

zbMATH Keywords

feature matchingminimax rate of separationpermutation estimation

Mathematics Subject Classification ID

Estimation in multivariate analysis (62H12) Pattern recognition, speech recognition (68T10) Integer programming (90C10)

Abstract: 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(logn)$, the rate is dimension free and equals $sigma(logn{)}^{1/2}$, where $sigma$ is the noise level. In contrast, when $d$ is larger than $clogn$ for some constant $c>0$, the minimax rate increases with $d$ and is of the order $sigma(dlogn{)}^{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.

Recommendations

• Optimality of the Least Sum of Logarithms in the Problem of Matching Map Recovery in the Presence of Noise and Outliers
• Optimal rates of statistical seriation
• Bayesian object matching
• A permutation test for matching and its asymptotic distribution
• Isotonic regression with unknown permutations: statistics, computation and adaptation

Cited in

(16)

• Linear regression with sparsely permuted data
• Optimal rates of statistical seriation
• Towards optimal estimation of bivariate isotonic matrices with unknown permutations
• Optimal detection of the feature matching map in presence of noise and outliers
• Isotonic regression with unknown permutations: statistics, computation and adaptation
• Iterative algorithm for discrete structure recovery
• Optimal full ranking from pairwise comparisons
• Estimation of Monge matrices
• Minimal model of permutation symmetry in unsupervised learning
• Optimal Permutation Recovery in Permuted Monotone Matrix Model
• Optimality of the Least Sum of Logarithms in the Problem of Matching Map Recovery in the Presence of Noise and Outliers
• Asymptotic mutual information in quadratic estimation problems over compact groups
• Covariance alignment: from maximum likelihood estimation to Gromov-Wasserstein
• Minimax optimal seriation in polynomial time
• Geometric planted matchings beyond the Gaussian model
• Robust point matching with distance profiles

Describes a project that uses

Uses Software

• SeDuMi
• SIFT
• SURF

This page was built for publication: Minimax rates in permutation estimation for feature matching

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2810764)