{"ID":6497861,"CreatedAt":"2026-07-13T01:19:40.13847098Z","UpdatedAt":"2026-07-14T01:36:59.12045529Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.09026","arxiv_id":"2607.09026","title":"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=ω(\\log n)$, under a Gaussian model with noise variance $σ^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\u003c2$, 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\u003eK/(K-1)$. Thus multiple views can break the impossibility barrier $b=2$ for the original matching problem: in particular, for $3/2 \u003c b \u003c 2$, the two-view model has no nontrivial recovery, but a third view makes all latent correspondences efficiently recoverable.","short_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=ω(\\log n)$, under a Gaussian model with noise variance $σ^2=d/(b\\log n)$, prior work identifies $b=2$ as the threshold for almost ex...","url_abs":"https://arxiv.org/abs/2607.09026","url_pdf":"https://arxiv.org/pdf/2607.09026v1","authors":"[\"Timothy L. H. Wee\",\"Kaylee Y. Yang\",\"Zhou Fan\",\"Cheng Mao\"]","published":"2026-07-10T01:17:10Z","proceeding":"math.ST","tasks":"[\"math.ST\",\"cs.DS\",\"math.PR\"]","methods":"[]","has_code":false}