Permutation estimation and minimax rates of identifiability

Olivier Collier 1, 2 Arnak S. Dalalyan 3
1 IMAGINE [Marne-la-Vallée]
LIGM - Laboratoire d'Informatique Gaspard-Monge, CSTB - Centre Scientifique et Technique du Bâtiment, ENPC - École des Ponts ParisTech
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 notion of the minimax rate of identifiability is introduced and its expression is obtained as a function of the sample size, noise level and dimensionality. We consider the cases of homoscedastic and heteroscedastic noise and carry out, in each case, upper bounds on the identifiability threshold of several estimators. This upper bounds are shown to be unimprovable in the homoscedastic setting. We also discuss the computational aspects of the estimators and provide empirical evidence of their consistency on synthetic data.
Type de document :
Article dans une revue
Liste complète des métadonnées
Contributeur : Olivier Collier <>
Soumis le : mercredi 13 février 2013 - 12:15:51
Dernière modification le : mardi 2 avril 2019 - 02:25:19
Document(s) archivé(s) le : samedi 1 avril 2017 - 23:22:19


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-00787916, version 1


Olivier Collier, Arnak S. Dalalyan. Permutation estimation and minimax rates of identifiability. JMLR, MIT Press, 2013, 31, pp.10-19. ⟨hal-00787916⟩



Consultations de la notice


Téléchargements de fichiers