Optimal Rates of Exact Recovery of the Matching Map

This lecture explores the problem of estimating matching maps between sequences of d-dimensional noisy observations of feature vectors with potentially different sizes. Begin with understanding permutation estimation before delving into the more complex challenge of estimating matching maps of unknown size k* < min(n, m). Discover how in high-dimensional settings, exact recovery of the true matching map is possible with high probability when the signal-to-noise ratio reaches at least order d^(1/4) - a rate proven to be optimal through corresponding lower bounds. Learn how this optimization problem can be reformulated as a minimum-cost flow problem and efficiently solved with complexity Õ(√k* n²). Examine numerical experiments on both synthetic and real-world data that illustrate these theoretical results and provide deeper insights into the estimators and algorithms. This research represents joint work with T. Galstyan, S. Hunanyan, and A. Dalalyan, presented by Arshak Minasyan from CentraleSupélec.