CS/IACS Faculty Colloq: Low Discrepancy Samplings of High Dimensional Geometric Spaces with Applications

Dates: 
Friday, June 26, 2015 - 14:00 to 15:30
Location: 
Room 120, New Computer Science Building

<p>Title: Low Discrepancy Samplings of High Dimensional Geometric Spaces with Applications Speaker: Prof. Chandrajit Bajaj, Department of Computer Science and Institute for Computational and Engineering Sciences (ICES), UT Austin Location: Room 120 in the New Computer Science Building (1st Floor Wireless Seminar Room Room) 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 bioinformatics. Bio: Chandrajit Bajaj is a Professor of Computer Science, and the director of the Center for Computational Visualization in the Institute for Computational and Engineering Sciences (ICES) at the University of Texas at Austin. Bajaj holds the Computational Applied Mathematics Chair in Visualization. He is also an affiliate faculty member of Mathematics, Bio-medical Engineering, the Institute of Cell and Molecular Biology and Neurosciences. He currently serves on the editorial boards for the International Journal of Computational Geometry and Applications, and the ACM Computing Surveys. He is a fellow of the American Association for the Advancement of Science (AAAS), the Association of Computing Machinery (ACM) and the Institute of Electrical and Electronic Engineers (IEEE).</p>

Computed Event Type: 
Mis
Event Title: 
CS/IACS Faculty Colloq: Low Discrepancy Samplings of High Dimensional Geometric Spaces with Applications