Les forêts couvrantes multi-types : un outil déterminantal ?
Hugo JAQUARD
Gipsa-lab, Université de Grenoble
Date(s) : 04/02/2025 iCal
14h30 - 15h30
Les estimateurs de Monte-Carlo sont des techniques importantes pour accélérer la résolution de problèmes calculatoires de grande échelle. Pour les problèmes formulés sur des graphes, ces méthodes se basent par exemple sur l’échantillonnage de marches aléatoires, ou de sous-graphes aléatoires du graphe d’origine. Certains problèmes nécessitent de considérer des graphes « enrichis », dont chaque arc décrit en plus une rotation ; c’est le cas par exemple de certains problèmes de lissage de fonctions définies sur graphes, d’interpolation ou de « synchronisation ». Cette structure additionnelle est appellée une « connection unitaire », et la littérature concernant les estimateurs de Monte-Carlo pour ces objets est très éparse.
Les forêts couvrantes multi-types sont une généralisation des forêts couvrantes à des graphes munis d’une connection unitaire. En particulier, ces structures sont associées à un processus ponctuel déterminantal sur le graphe, et l’exposé se concentrera sur la description et l’utilisation de ces outils pour résoudre un problème de lissage par Monte-Carlo. On obtient notamment un résultat d’approximation en moyenne, et un algorithme « à la Wilson » pour échantillonner ces forêts. En outre, il est facile d’obtenir des résultats de concentrations pour ces estimateurs, et l’on explore des liens avec des estimateurs « à la Feynman-Kac » pour ces problèmes.
Selon le temps, on pourra évoquer des généralisations aux complexes simpliciaux ou, dans une perspective applicative, des comparaisons numériques avec des outils standards.
Ce travail a été réalisé durant ma thèse, sous la supervision de Pierre-Olivier Amblard, Simon Barthelmé et Nicolas Tremblay
Emplacement
I2M Saint-Charles - Salle de séminaire
Catégories
