Low Discrepancy Samplings of High Dimensional Geometric Spaces with Applications

Abstract: Generating nearly uniform random point samples from geometric spaces is fundamental to several applications in the computational and data sciences. One natural measure of uniform sampling quality is discrepancy. In this talk I shall describe deterministic methods of constructing low discrepancy samplings of geometric spaces, with particular emphasis on motion groups. These include a deterministic method of constructing an m point set sampling of the rotation group SO(3) with discrepancy O(( log^(2/3) m ) / m^(1/3)) against collections of local convex sets (suitably defined under the Hopf Fibration). We then extend this construction to get an almost exponential improvement in size (from the trivial tensor product) of low discrepancy samplings in SO(3)^n . Using  low discrepancy sets of size m for SO(3) we construct a collection of (mn/e)^(O(loglog(m) + (loglog(1/e))(logloglog(1/e)))) points (as opposed to O(m^n) size) and with discrepancy e against the class of combinatorial rectangles. These low discrepancy samplings of product spaces coupled to non-equispaced SO(3) Fourier transforms provides efficient space-time and bounded error complexity solutions for high dimensional non-convex geometric optimization, numerical integration and uncertainty quantification. An example application of this methodology shall be shown from molecular bio-informatics.