Robust Point Matching with Distance Profiles
This provides theoretical foundations for widely used but under-analyzed matching procedures in fields like computer vision or data analysis, though it is incremental as it builds on existing ideas.
The paper tackles the problem of robust point matching in the presence of outliers and noise by analyzing procedures based on distance profiles, showing that under certain probabilistic settings, the method succeeds with high probability and connects it to the Gromov-Wasserstein distance with a new sample complexity result.
We show the outlier robustness and noise stability of practical matching procedures based on distance profiles. Although the idea of matching points based on invariants like distance profiles has a long history in the literature, there has been little understanding of the theoretical properties of such procedures, especially in the presence of outliers and noise. We provide a theoretical analysis showing that under certain probabilistic settings, the proposed matching procedure is successful with high probability even in the presence of outliers and noise. We demonstrate the performance of the proposed method using a real data example and provide simulation studies to complement the theoretical findings. Lastly, we extend the concept of distance profiles to the abstract setting and connect the proposed matching procedure to the Gromov-Wasserstein distance and its lower bound, with a new sample complexity result derived based on the properties of distance profiles. This paper contributes to the literature by providing theoretical underpinnings of the matching procedures based on invariants like distance profiles, which have been widely used in practice but have rarely been analyzed theoretically.