Thesis of Loïs Paulin


Subject:
Exploration of the structure of sample for Monte Carlo applications

Start date: 26/11/2019
Defense date: 17/04/2023

Advisor: Victor Ostromoukhov

Summary:

Numerically computing a function integral is an essential task for many applications in computer science.Be it in finance, geometry, physical simulations and many other domains.However, classical numerical methods (Newton, Simpson), require a number of function evaluations that grows exponentially with the dimension.Monte Carlo methods have been introduced in order to palliate this issue.They estimate the integral as the mean of randomly positioned evaluations of the function.The choice of these positions is crucial to a good convergence of the estimation.Many quality measures exist to qualify point sets with each their own strength and weaknesses depending on applications.In this thesis, we propose efficient methods to optimize these quality measures and adapt them to the needs of diverse applications.We first interested ourselves in optimal transport which is a precious tool to generate samples but which presents computational issues in high dimensions.Based on the recent advances in the sliced formulation of optimal transport, we put together an efficient sampler generating samples of high quality which was demonstrated in rendering applications.We then interested ourselves in the construction of low discrepancy samples, a well-liked quality measure for the strength of the theorems linking it to integration and for the elegant algebraic structure minimizing it.These structures have been built in an abstract setting and thus lack properties required by applications that also need a ''projective'' uniformity.Starting from the well-known Sobol' construction we created a new high-dimensional sampler providing a perfect 2D uniformity for all pairs of consecutive dimensions.This property has long been judged impossible to attain and provides an extra boost of quality to renderings.However, projective uniformity on consecutive dimensions is only interesting in a few applications.Using the theoretical proof of the properties of our previous sampler we were able to design a solver that can generate low discrepancy point sets with any targeted and theoretically possible projective property.This work is based on a new approach of fundamental theorems of low discrepancy constructions from the linear algebra point of view instead of the classical combinatorial one.All these results led to three publications at SIGGRAPH conferences, one at MCQMC and also new research perspectives discussed in this thesis.


Jury:
Mme Bouakaz SaidaProfesseur(e)LIRIS Université Claude Bernard Lyon 1Examinateur​(trice)
M. Boubekeur TamyDirecteur(trice) de rechercheAdobe Research ParisExaminateur​(trice)
Mme Chaîne RaphaëlleProfesseur(e)LIRIS Université Claude Bernard Lyon 1Examinateur​(trice)
M. Drettakis Directeur(trice) de rechercheINRIA Sophia AntipolisRapporteur(e)
M. Holzschuch NicolasDirecteur(trice) de rechercheINRIA SaintIsmierExaminateur​(trice)
Mme Lemieux ChristianeProfesseur(e)Université de Waterloo (Canada)Président(e)
M. Levy BrunoDirecteur(trice) de rechercheINRIA NancyExaminateur​(trice)
M. Ostromoukhov VictorProfesseur(e)LIRIS Université Lyon 1Directeur(trice) de thèse