Papers › Geometric planted matchings beyond the Gaussian model
Geometric planted matchings beyond the Gaussian model
Lucas da Rocha Schwengber, Roberto Imbuzeiro Oliveira
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
We consider the problem of recovering an unknown matching between a set of n randomly placed points in ℝᵈ and random perturbations of these points. This can be seen as a model for particle tracking and more generally, entity resolution. We use matchings in random geometric graphs to derive minimax lower bounds for this problem that hold under great generality. Using these results we show that for a fixed d, as long as the noise distribution has finite d-th moment, and both initial positions and noise have bounded continuous densities, the minimax rate for the problem scales as Θ(n²σᵈ ∧n). Under the stronger assumptions that the tail of the noise is sub-Gaussian, we show that the order of the number of mistakes made by an estimator that minimizes the sum of squared Euclidean distances is minimax optimal when d is fixed and is optimal up to nᵒ⁽¹⁾ factors when d = o(logn). In the high-dimensional regime we consider a setup where both initial positions and perturbations have independent sub-Gaussian coordinates. In this setup we give sufficient conditions under which the same estimator makes no mistakes with high probability. We prove an analogous result for an adapted version of this estimator that incorporates information on the covariance matrix of the perturbations.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections