Variance Analysis for Monte Carlo Integration

Adrien Pilleboue 1   Gurprit Singh 1   David Coeurjolly 2   Michael Kazhdan 3   Victor Ostromoukhov 1,2

Joint first authors   1 Universit√© Lyon 1   2 CNRS-LIRIS UMR5205   3 Johns Hopkins University

SIGGRAPH / ACM Transactions on Graphics 34(4) 2015

Abstract

We propose a new spectral analysis of the variance in Monte Carlo integration, expressed in terms of the power spectra of the sampling pattern and the integrand involved. We build our framework in the Euclidean space using Fourier tools and on the sphere using spherical harmonics. We further provide a theoretical background that explains how our spherical framework can be extended to the hemispherical domain. We use our framework to estimate the variance convergence rate of different state-of-the-art sampling patterns in both the Euclidean and spherical domains, as the number of samples increases. Furthermore, we formulate design principles for constructing sampling methods that can be tailored according to available resources. We validate our theoretical framework by performing numerical integration over several integrands sampled using different sampling patterns.

Paper

Additional Materials

Video download (HD)

Code (samplers, analysis tools...)

Additional techreport: Variance Analysis for Monte Carlo Integration: A Representation-Theoretic Perspective, Michael Kazhdan, Gurprit Singh, Adrien Pilleboue, David Coeurjolly, Victor Ostromoukhov, arXiv:1506.00021

Fast-forward video (youtube)

BibTeX

@article{Pilleboue:2015:VAMCI,
author = {Pilleboue, Adrien and Singh, Gurprit and Coeurjolly, David and Kazhdan, Michael and Ostromoukhov, Victor},
title = {Variance Analysis for Monte Carlo Integration},
journal = {ACM Trans. Graph. (Proc. SIGGRAPH)},
volume = {34},
number = {4},
year = {2015},
pages= {124:1--124:14},
publisher = {ACM},
address = {New York, NY, USA},
abstract= {We propose a new spectral analysis of the variance in Monte Carlo integration, expressed in terms of the power spectra of the sampling pattern and the integrand involved. We build our framework in the Euclidean space using Fourier tools and on the sphere using spherical harmonics. We further provide a theoretical background that explains how our spherical framework can be extended to the hemispherical domain. We use our framework to estimate the variance convergence rate of different state-of-the-art sampling patterns in both the Euclidean and spherical domains, as the number of samples increases. Furthermore, we formulate design principles for constructing sampling methods that can be tailored according to available resources. We validate our theoretical framework by performing numerical integration over several integrands sampled using different sampling patterns.}
}

Acknowledgements

This project is supported by the ANR excellence chair (ANR-10-CEXC-002-01) and digitalSnow/digitalfoam programs (ANR-11-BS02-009 and PALSE/2013/21). We thank the anonymous reviewers for their detailed feedback to improve the final version of the paper, Mathieu Desbrun, Katherine Breeden, Jonathan Dupuy, Nicolas Bonneel and Brian Wyvill for proof reading the paper and giving their insightful comments, Jean-Claude Iehl and Vincent Nivoliers for their active participation, and Kartic Subr for the discussions that ultimately led to this paper. Our special thanks to David Kazhdan for helping us in developing rigorous proofs.