Optimality of the Least Sum of Logarithms in the Problem of Matching Map Recovery in the Presence of Noise and Outliers

Tigran Galstyan; Arshak Minasyan

doi:10.52737/18291163-2023.15.5-1-9

Authors

Tigran Galstyan Russian-Armenian University; Yerevan State University
Arshak Minasyan CREST, ENSAE, IP Paris

DOI:

https://doi.org/10.52737/18291163-2023.15.5-1-9

Keywords:

Multidimensional Statistics, Vector Matching, Separation Rate

Abstract

We consider the problem of estimating the matching map between two sets of feature-vectors observed in a noisy environment and contaminated by outliers. It was already known in the literature that in the outlier-free setting, the least sum of squares (LSS) and the least sum of logarithms (LSL) are both minimax-rate-optimal. It has been recently proved that the optimality properties of the LSS continue to hold in the case the data sets contain outliers. In this work, we show that the same is true for the LSL as well. Therefore, LSL has the same desirable properties as the LSS, and, in addition, it is minimax-rate-optimal in the outlier-free setting with heteroscedastic noise.

References

G. Bökman and F. Kahl, A case for using rotation invariant features in state of the art feature matchers. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) Workshops (2022), pp. 5110-5119. https://doi.org/10.1109/CVPRW56347.2022.00559

T. Cai and R. Ma, Matrix reordering for noisy disordered matrices: optimality and computationally efficient algorithms. Preprint (2022), ArXiv:2201.06438.

O. Collier and A.S. Dalalyan, Minimax rates in permutation estimation for feature matching. Journal of Machine Learning Research, 17 (2016), no. 6, pp. 1-31.

T. Galstyan, A. Minasyan and A. Dalalyan, Optimal detection of the feature matching map in presence of noise and outliers. Electronic Journal Of Statistics, 16 (2022), pp. 5720-5750. https://doi.org/10.1214/22-ejs2076

A. Minasyan, T. Galstyan, S. Hunanyan and A. Dalalyan, Matching map recovery with an unknown number of outliers. Preprint (2022), ArXiv:2210.13354.