Statistical and Computational Complexity of the Feature Matching Map Detection Problem

Tigran Galstyan (Univ. Paris Saclay, CNRS, CentraleSupélec, L2S)
October 17, 2025 — 11:00 — "new L2S location (IBM building), Room Hopper (Third floor)" (and Teams)

Abstract

The problem of finding the best matching between two point clouds has been extensively studied, both theoretically and experimentally. The matching problem arises in various applications, for instance in computer vision, bioinformatics and natural language processing. In computer vision, finding the correspondence between two sets of local descriptors extracted from two images of the same scene is a well-known example of a matching problem. When datasets do not contain outliers, meaning that both matching sets have the same size and all points have their corresponding match in the other dataset, the optimality of the matching procedures was previously studied from a minimax statistical viewpoint. Clearly, in aforementioned applications, not all the points have their matching point and one can hardly know in advance how many points have their corresponding matching points. This work focuses on various extended settings of the problem (i.e. containing outliers) and gaining a theoretical understanding of the statistical limitations of the matching problem.