Permutation estimation and minimax rates of identifiability

Olivier Collier, Arnak Dalalyan
Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics, PMLR 31:10-19, 2013.

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 matching threshold 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 matching 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 some empirical evidence of their consistency on synthetic data-sets.

Cite this Paper

BibTeX
@InProceedings{pmlr-v31-collier13a, title = {Permutation estimation and minimax rates of identifiability}, author = {Collier, Olivier and Dalalyan, Arnak}, booktitle = {Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics}, pages = {10--19}, year = {2013}, editor = {Carvalho, Carlos M. and Ravikumar, Pradeep}, volume = {31}, series = {Proceedings of Machine Learning Research}, address = {Scottsdale, Arizona, USA}, month = {29 Apr--01 May}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v31/collier13a.pdf}, url = {https://proceedings.mlr.press/v31/collier13a.html}, 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 matching threshold 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 matching 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 some empirical evidence of their consistency on synthetic data-sets.}, note = {Notable paper award} }
Endnote
%0 Conference Paper %T Permutation estimation and minimax rates of identifiability %A Olivier Collier %A Arnak Dalalyan %B Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2013 %E Carlos M. Carvalho %E Pradeep Ravikumar %F pmlr-v31-collier13a %I PMLR %P 10--19 %U https://proceedings.mlr.press/v31/collier13a.html %V 31 %X 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 matching threshold 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 matching 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 some empirical evidence of their consistency on synthetic data-sets. %Z Notable paper award
RIS
TY - CPAPER TI - Permutation estimation and minimax rates of identifiability AU - Olivier Collier AU - Arnak Dalalyan BT - Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics DA - 2013/04/29 ED - Carlos M. Carvalho ED - Pradeep Ravikumar ID - pmlr-v31-collier13a PB - PMLR DP - Proceedings of Machine Learning Research VL - 31 SP - 10 EP - 19 L1 - http://proceedings.mlr.press/v31/collier13a.pdf UR - https://proceedings.mlr.press/v31/collier13a.html AB - 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 matching threshold 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 matching 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 some empirical evidence of their consistency on synthetic data-sets. N1 - Notable paper award ER -
APA
Collier, O. & Dalalyan, A.. (2013). Permutation estimation and minimax rates of identifiability. Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 31:10-19 Available from https://proceedings.mlr.press/v31/collier13a.html. Notable paper award

Related Material