Research Talk | Approximate Geometry in General Dimension: Search, Clustering, Sampling

Feb 13 2019 11:00 AM - Feb 13 2019 12:00 PM

-By Professor Ioannis Z. Emiris (NKU Athens and ATHENA Research Innovation, Greece)


In handling and analyzing modern geometric data, it is indispensable to treat dimension as an input parameter and design algorithms that address the curse of dimensionality. The talk's main focus is on approximate search among pointsets. The predominant paradigm from Computational Geometry relies on tree-based space partitions that exhibit complexity exponential in the dimension. Locality Sensitive Hashing achieves polynomial dependence in the dimension but requires subquadratic space usage. We follow a different tack by generalizing the celebrated Johnson-Lindenstrauss Lemma to design simple, randomized projections, which achieve competitive query complexity but also optimal space and construction-time complexities.

We extend these methods to products of Euclidean metrics, which generalize the discrete Frechet and Dynamic time warping distances on one-dimensional objects. Moreover, our tools have been employed in an "inverse" assignment step to accelerate Lloyd's algorithm for k-means clustering of massive image datasets. Here and in general, our work is motivated by expressive, yet high-dimensional representations of complex objects, such as those currently produced by deep neural networks. 

Membership oracle in convex polytopes may be reduced to nearest neighbor search and can thus benefit from the above technology: it may then serve as basis for polynomial-time methods for approximating volume. If time permits, I shall discuss this problem, starting with today's record-complexity approaches that rely on uniform sampling. The latter is typically computed by Monte Carlo geometric walks, given the region's boundary. We have developed practical Hit-and-Run algorithms that led to the first efficient, public-domain software handling inputs in 100 dimensions or beyond. More recently, we considered nonlinear convex regions arising in finance applications, as well as polytopes given as a convex hull of their vertices.

More Information 

Wednesday, February 13, 11:00 AM

Building 1, level 2, Room 2202