Halftoning and quasi-Monte Carlo

Ken Hanson, CCS-2
(slides)

Abstract

In quasi-Monte Carlo, the aim is to develop point sets for sampling a function that provide more accurate estimates of multi-dimensional integrals of certain classes of functions than randomly chosen points. The general notion in QMC is to avoid the clumpiness of random points by spreading them out as much as possible. This same goal is also sought after in digital halftoning, a technique used in printing to render a gray-scale image by placing black dots on a page. I will describe an approach to generating QMC point sets, which I call Minimum Visual Discrepancy (MVD), because it is derived from digital halftoning ideas, that proves to produce point sets with even better integration accuracy than standard QMC sequences on a series of 2D test problems. It can be shown that the MVD algorithm is equivalent to formulating the problem in terms of a collection of interacting particles that repel each other, constrained to the integration region. This formulation is suitable for moderately high dimensions.

I will also mention an idea for improving the standard Monte Carlo approximation to an integral by weighting sampled function values by their Voronoi volumes. This approach improves the integration accuracy of standard MC by a large factor in 2D, but unfortunately not by very much in higher dimensions. (see paper)

Keywords: Quasi-Monte Carlo, Monte Carlo integration, low-discrepancy sequences, Halton sequence, Sobel sequence, halftoning, direct binary search, minimum visual discrepancy, Voronoi analysis, Voronoi-weighted Monte-Carlo integration