Geometric planted matchings in high dimensions: The power of multiple views

Abstract

We study the problem of recovering the correspondence between a collection of $n$ points in ${\mathbb{R}}^d$ and a noisy, permuted version of those points. In the high-dimensional regime $d=\omega (\log n)$, under a Gaussian model with noise variance ${\sigma }^2=d/(b\log n)$, prior work identifies $b=2$ as the threshold for almost exact recovery. We prove that this threshold is all-or-nothing: for every fixed $b<2$, no estimator recovers a positive fraction of the matching, and even estimating the matched point cloud in Euclidean distance is asymptotically no better than ignoring the correspondence. On the other hand, we consider a multi-view generalization of the problem where $K$ noisy, independently permuted copies of the same latent point cloud are observed. Here we show that a simple polynomial-time procedure recovers all relative matchings up to $o(n)$ errors whenever $b>K/(K-1)$. Thus multiple views can break the impossibility barrier $b=2$ for the original matching problem: in particular, for $3/2<b<2$, the two-view model has no nontrivial recovery, but a third view makes all latent correspondences efficiently recoverable.