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

估计函数的积分形成了许多一般类问题的基石，例如优化，采样和归一化;这些问题反过来又是计算机图形学，计算机视觉和机器学习等各个领域的大量应用的核心工具。被积函数或被积函数是复杂的，很少以封闭形式存在。它的域跨越任意高维的空间。精确积分是无望的，近似在实践中是不可避免的。积分的估计通常使用在域中的多个采样位置处的被积函数的评估来构造。对函数进行采样的点集通常统称为采样模式。对于计算机图形应用，一个长度为1.5h的现代动画长片通常涉及到生成总共几百万亿个映射到光路中的高维样本，尽管已经提出了许多策略来生成样本，但是测量高维样本模式的质量是一个悬而未决的问题。采样策略目前是在个案的基础上进行比较，明确计算每个应用程序的上下文中的错误独立。与诸如差异和傅立叶分析之类的测量相关联的计算随着维度呈指数级缩放，因此对于高维域中的样本是不可行的。拟议的工作旨在量化的高维点集的equidistribution使用的替代措施，是听话的差异。本计画将建立计算拓扑学、随机几何学与蒙地卡罗积分误差分析之间的数学联系。我们的目标是制定一个衡量标准，纯粹根据所使用的样本评估基于抽样的估计质量。衍生的理论将被评估和应用于计算机图形学应用程序的蒙特卡罗渲染。

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.