Random Multi-Type Spanning Forests for Synchronization on Sparse Graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913543825129472 |
|---|---|
| author | Jaquard, Hugo Amblard, Pierre-Olivier Barthelmé, Simon Tremblay, Nicolas |
| author_facet | Jaquard, Hugo Amblard, Pierre-Olivier Barthelmé, Simon Tremblay, Nicolas |
| contents | Random diffusions are a popular tool in Monte-Carlo estimations, with well established algorithms such as Walk-on-Spheres (WoS) going back several decades. In this work, we introduce diffusion estimators for the problems of angular synchronization and smoothing on graphs, in the presence of a rotation associated to each edge. Unlike classical WoS algorithms that are point-wise estimators, our diffusion estimators allow for global estimations by propagating along the branches of random spanning subgraphs called multi-type spanning forests. Building upon efficient samplers based on variants of Wilson's algorithm, we show that our estimators outperform standard numerical-linear-algebra solvers in challenging instances, depending on the topology and density of the graph. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_19300 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Random Multi-Type Spanning Forests for Synchronization on Sparse Graphs Jaquard, Hugo Amblard, Pierre-Olivier Barthelmé, Simon Tremblay, Nicolas Probability Data Structures and Algorithms Statistics Theory Random diffusions are a popular tool in Monte-Carlo estimations, with well established algorithms such as Walk-on-Spheres (WoS) going back several decades. In this work, we introduce diffusion estimators for the problems of angular synchronization and smoothing on graphs, in the presence of a rotation associated to each edge. Unlike classical WoS algorithms that are point-wise estimators, our diffusion estimators allow for global estimations by propagating along the branches of random spanning subgraphs called multi-type spanning forests. Building upon efficient samplers based on variants of Wilson's algorithm, we show that our estimators outperform standard numerical-linear-algebra solvers in challenging instances, depending on the topology and density of the graph. |
| title | Random Multi-Type Spanning Forests for Synchronization on Sparse Graphs |
| topic | Probability Data Structures and Algorithms Statistics Theory |
| url | https://arxiv.org/abs/2403.19300 |