Integral Estimation from Point Cloud in d-Dimensional Space: a Geometric View

Chuanjiang Luo, Jian Sun and Yusu Wang

 

Abstract

Integration over a domain, such as a Euclidean space or a Riemannian manifold, is a fundamental problem across scientific fields. Many times, the underlying domain is only accessible through a discrete approximation, such as a set of points sampled from it, and it is crucial to be able to estimate integral in such discrete settings. In this paper, we study the problem of estimating the integral of a function defined over a k-submanifold embedded in Rd, from its function values at a set of sample points. Previously, such estimation is usually obtained in a statistical setting, where input data is typically assumed to be drawn from certain probabilistic distribution. Our paper is the first to consider this important problem of estimating integral from point clouds data (PCD) under the more general non-statistical setting, and provide certain theoretical guarantees.

Our approaches consider the problem from a geometric point of view. Specifically, we estimate the integral by computinga weighted sum, and propose two weighting schemes: the Voronoi and the Principal Eigenvector schemes. The running time of both methods depends mostly on the intrinsic dimension of the underlying manifold, instead of on the ambient dimensions. We show that the estimation based on the Voronoi scheme converges to the true integral under the so-called (ε, δ)-sampling condition with explicit error bound presented. This is the first result of this sort for estimating integral from general PCD. For the Principal Eigenvector scheme, although no theoretical guarantee is established, we present its connection to the Heat diffusion operator, and illustrate justifications behind its construction. Experimental results show that both new methods consistently produce more accurate integral estimations than common statistical methods under various sampling conditions.

  

Download

All data and software can be downloaded for free via the following link

Integral.zip

Citation

If you use any part of this code, please cite:
 

 

Feedback

Please send email to us if you have any questions

Last updated: Jul, 25, 2009