Holey Sampling: Topological Analysis of Sampling Patterns for Assessing Error in High-dimensional Quadrature

点击翻译按钮获取中文摘要

Estimating integrals of functions forms the cornerstone of many general classes of problems such as optimisation, sampling and normalisation; these problems, in turn, are central tools for a plethora of applications across various fields such as computer graphics, computer vision and machine learning. The integrand, or function to be integrated, is complicated and rarely available in closed form. Its domain spans spaces of arbitrarily high dimensionality. Exact integration is hopeless and approximation is unavoidable in practice. An estimate of the integral is typically constructed using evaluations of the integrand at a number of sampled locations in the domain. The set of points where the function is sampled is often referred to collectively as a sampling pattern. For computer graphics applications, a modern animation feature film of length 1.5h typically involves the generation of a total of a few hundreds of trillions of high-dimensional samples that are mapped into light paths.Although a number of strategies have been proposed towards generating samples, measuring the quality of high-dimensional sampling patterns is an open problem. Sampling strategies are currently compared on a case-by-case basis by explicitly computing errors in the context of each application independently. The computation associated with measures such as discrepancy and Fourier analysis scale exponentially with dimensionality and are therefore not practicable for samples in high-dimensional domains. The proposed work seeks to quantify equidistribution of high-dimensional point sets using an alternative measure to discrepancy that is tractable. This project will establish mathematical connections between computational topology, stochastic geometry and error analysis for Monte Carlo integration. The goal is to develop a measure for assessing the quality of sampling-based estimators purely based on the samples used. The derived theory will be evaluated and applied on Monte Carlo rendering for Computer Graphics applications.