Échantillonner des géométries non-euclidiennes par transport optimal

Si le transport optimal n'est pas un sujet neuf, il continue de susciter un grand intérêt, en partie grâce aux nombreux progrès théoriques et numériques qui y ont été faits dans le domaine de l’approximation des fonctions de densité de probabilité à partir d’échantillonnage de l’espace considéré de travail. La théorie du transport optimal s'appuie sur la distance de Wasserstein. Outil majeur issu des mathématiques appliquées, elle permet de quantifier la distance entre deux mesures de probabilités au sens du moindre effort, afin de transporter la masse d'une mesure sur l'autre étant donnée une fonction de coût. L'intérêt de l'outil réside dans la généricité des mesures qui peuvent être considérées : mesures discrètes (des ensembles de points, par exemple), des histogrammes, ou des mesures continues. Ainsi, si la distance de Wasserstein entre un ensemble de points et une distribution uniforme sur un domaine est très petite, ces points remplissent harmonieusement ce domaine. Cette caractéristique de remplissage harmonieux de l'espace par un ensemble de points est appelée «bruit bleu» en informatique graphique. Générer du bruit bleu de manière générique n'est pas une chose simple, mais la théorie du transport optimal permet d’y parvenir.

En revanche, le calcul de la distance de Wasserstein peut être lourd en termes de ressources computationnelles. Pour pallier cette limitation d’implantation, David Coeurjolly, directeur de recherche CNRS au Laboratoire d’informatique en image et systèmes d’information (LIRIS – CNRS/ INSA de Lyon/Université Claude Bernard Lyon 1), Nicolas Courty, professeur à l’Université de Bretagne Sud, membre de l’IRISA Institut de recherche en informatique et systèmes aléatoires (IRISA - CNRS/Université de Rennes 1) et Baptiste Genest, étudiant à l’Université Claude Bernard Lyon 1 se sont intéressés à une propriété du transport optimal qui, bien que compliqué en toutes dimensions, l’est beaucoup moins en dimension 1 ou 1D (appariement optimal donné par un simple tri des échantillons). De nombreux travaux ont proposé une approximation avec garanties, dites par «tranche» ou «coupe» de la distance de Wasserstein (Sliced Wasserstein distance) dans ce contexte. Elle consiste à moyenner des distances de Wasserstein 1D évaluées à partir de mesures projetées sur des directions aléatoires. Cette approche est une très bonne approximation, qui dépend très peu de la dimension du problème et pour laquelle de nombreux algorithmes efficaces existent.

Ainsi, ces deux idées peuvent être combinées pour générer du bruit bleu par du transport optimal de manière efficace dans n'importe quelle dimension. La méthode part d'un ensemble de points initial, qui ne possède pas les caractéristiques du bruit bleu mais qui est simple à générer, puis la position de chaque point est optimisée de telle sorte qu'à chaque itération la Sliced Wasserstein Distance est réduite entre ces points et la distribution cible. Cette idée avait déjà été explorée par des travaux précédents, notamment au LIRIS ; la contribution majeure du travail réalisé ici réside dans l'extension de cette procédure à des géométries «non-euclidiennes».

Les géométries non-euclidiennes sont des concepts fondamentaux en mathématiques. Ce sont les exemples les plus simples d'espaces qui ne soient pas plats (à l'inverse d'un plan par exemple). Pour les citer : la sphère, dite à courbure positive, et le plan hyperbolique, qui a une courbure négative. Si les auteurs de l’article n’ont pas introduit la Sliced Wasserstein Distance sur ces espaces particuliers (ce travail fut mené par Clément Bonet, ancien doctorant de Nicolas Courty, co-auteur de l'article, aujourd’hui post-doctorant au Centre de recherche en économie et stastistique (CREST – CNRS/École polytechnique/Groupe des écoles nationales économie et statistique)), ils ont trouvé une traduction efficace de cette procédure d’échantillonnage sur ces géométries non-euclidiennes.

En termes d'applications dans le domaine de l’informatique graphique et de la géométrie, puisque les géométries non-euclidiennes sont des espaces intrinsèquement courbés, il est désormais plus simple d'échantillonner des géométries plus génériques. Ils appliquent cette procédure pour échantillonner des maillages (en passant par une correspondance entre le maillage et la sphère, soit le plan hyperbolique) de manière intrinsèque (ce qui signifie que le résultat est indifférent au fait que la surface s'auto-intersecte par exemple). Leur contribution permet également d’échantillonner ce qu'on appelle le "plan projectif", et ainsi générer des ensembles harmonieux de rotations, de directions, etc.