Statistical and Computational Complexity of the Feature Matching Map Detection Problem

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 contains 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 thoroughly studied in Collier and Dalalyan (2016a) 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. The goal of the present work is to focus on various extended settings of the problem (i. e. containing outliers) and to gain a theoretical understanding of the statistical limitations of the matching problem.