Random Multi-Type Spanning Forests for Synchronization on Sparse Graphs
<|reference_start|>Random Multi-Type Spanning Forests for Synchronization on Sparse Graphs: 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, these estimators allow for global estimations by propagating along the branches of multi-type spanning forests, and we show that they can outperform standard numerical-linear-algebra solvers in challenging instances, depending on the topology and density of the graph.<|reference_end|>
@article{jaquard2024random,
    title={Random Multi-Type Spanning Forests for Synchronization on Sparse Graphs},
    author={Hugo Jaquard, Pierre-Olivier Amblard, Simon Barthelm'e, Nicolas
  Tremblay},
    journal={arXiv preprint arXiv:2403.19300},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.19300},
    primaryClass={math.PR cs.DS math.ST stat.TH}
}