An importance sampling in N Sphere Monte Carlo and its performance analysis for high dimensional integration

Abstract

Statistical methods for estimating integrals are indispensable when the number of dimensions (parameters) become greater than ~ 10, where numerical methods are unviable in general. Well-known statistical methods like Quasi-Monte Carlo converge quickly only for problems with a small number of effective dimensions, and Markov Chain Monte Carlo (MCMC) methods incur a sharply increasing computing effort with the number of dimensions 'n' that is bounded as O(n^5). This bound on the dimensional scaling of computing effort in multiphase MCMC is limited to domains with a given convex shape (determined by the limits of integration). Note that the non-convexity and roughness of the boundaries of the domain are factors that adversely affect the convergence of such methods based on a random walk in high dimensions. A different approach to high-D integration using (1D) line integrals along random directions coupled with a less-known volume transformation was suggested here at the Institute by Arun et. al. This method called as N-sphere Monte Carlo (NSMC) is agnostic to the shape and roughness of the boundary for any given distribution of extents of the domain from a reference point. While the dimensional scaling of computing in NSMC integration can be bound as O(n^3) for any distribution of relative extents (and not a particular convex shape), a similar bound does not exist for MCMC as any given extent distribution can represent numerous geometries where it may not converge. It was shown earlier that when restricted to convex shapes where the extent density functions become increasingly heavy tailed as 'n' increases, the naive NSMC may be more efficient than the multiphase MCMC only when n < ~100. This thesis has three contributions. 1) It is analytically shown that, unlike MCMC, the convergence of NSMC in the estimation of n-volume of a domain is not a necessary condition for its convergence in any other integration over that domain. 2) A direct numerical comparison of the naive NSMC and the multiphase MCMC was performed for estimating n-volumes and different types of integrands, establishing this advantage in integration even over typical convex domains when n < ~ 100. 3) A method for importance sampling is suggested for NSMC with a demonstration of the improved performance in higher dimensions for domains with heavy tailed extent density functions. In identifying and ensuring a local volume of interest is sampled adequately, this method employs efficient sampling in high-D cones with a target distribution.