Uncertainty Quantification Working Group
September 18, 11:30 AM, CNLS Conf. Room, TA-3, Bldg. 1690

Halftoning and quasi-Monte Carlo

Ken Hanson, CCS-2


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)