EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Geometric Planted Matchings Beyond the Gaussian Model

Lucas R. Schwengber, Roberto I. Oliveira

Random Structures & Algorithms · 2026-07 · 68 (4)

DOI: 10.1002/rsa.70080 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Random Structures & Algorithms, online erschienen am 11.06.2026. Verfasst von Lucas R. Schwengber und 1 weiteren Autor:innen. Die Arbeit nennt 24 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Fundação Carlos Chagas Filho de Amparo à Pesquisa do Estado do Rio de Janeiro, Conselho Nacional de Desenvolvimento Científico e Tecnológico.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We consider the problem of recovering an unknown matching between a set of 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 , as long as the noise distribution has finite th moment, and both initial positions and noise have bounded continuous densities, the minimax rate for the problem scales as . 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 is fixed and is optimal up to factors when . 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.

Förderung

  • Fundação Carlos Chagas Filho de Amparo à Pesquisa do Estado do Rio de Janeiro
  • Conselho Nacional de Desenvolvimento Científico e Tecnológico

Zitieren

APA

Schwengber, L. R., & Oliveira, R. I. (2026). Geometric Planted Matchings Beyond the Gaussian Model. Random Structures & Algorithms, 68(4). https://doi.org/10.1002/rsa.70080

Vancouver

Schwengber LR, Oliveira RI. Geometric Planted Matchings Beyond the Gaussian Model. Random Structures & Algorithms. 2026;68(4). doi:10.1002/rsa.70080

BibTeX
@article{Schwengber2026,
  author = {Schwengber, Lucas R. and Oliveira, Roberto I.},
  title = {Geometric Planted Matchings Beyond the Gaussian Model},
  journal = {Random Structures & Algorithms},
  year = {2026},
  volume = {68},
  number = {4},
  doi = {10.1002/rsa.70080}
}
Kostenlos starten →