Algorithms for Multi-Dimensional Data via Sketches – ADDS

The project can be divided into three tasks:

Task 1: The study of samples and succinct approximations of geometric data---including a better understanding of the discrete structure of geometric data in high dimensions; notions of sampling complexity; their statistical, geometric and combinatorial properties; dimension-independent structures in geometry; construction and algorithms for succinct approximations; role and limits of random sampling.

Task 2: The use of samples and succinct approximations to design improved sketches of geometric data---including core-sets for shape-fitting problems; kernels for extent-based problems; depth-estimation for shape-approximation; polytope approximation for approximate nearest-neighbors.

Task 3: The use of sketches to design effective approximation algorithms to optimization problems---including algorithms for data-depth in high dimensions, chance-based optimization, nearest-neighbour in non-Euclidean metrics; the efficient implementations of these algorithms; testing and evaluation; development of an open-source library.

Our work so far has resolved or improved upon a number of open problems:

-The work of Guilherme Dias da Fonseca and his colleagues achieves a major breakthrough by resolving the decades-old problem of approximating a closed, convex set K in Euclidean d-dimensional space by a convex polytope of low combinatorial complexity.

-The solutions to instances of hard problems of coordinated motion planning won the international challenge CG:SHOP2021 associated to the conference SoCG.

-In collaboration with Imre Bárány, we presented improved bounds for the depth of Radon points in Euclidean spaces.

-The multiplicative weights update technique was used to improve the running time of constructing low crossing matchings, improving the previous-best general bound from 1989.

Improvements in sketches could potentially lead to breakthroughs in many geometric optimization problems. Each one of these domains of geometric optimization is already interesting by itself but as these algorithms are the tools of scientific computations in many different areas, improving one of them implies impacting many different domains: Linear, bilinear or integer programming are, for instance, the computational core of combinatorial optimization and operations research; visibility computations are the computational core of rendering in computer graphics; nearest neighbor search has applications in DNA sequencing, chemical similarity, pattern recognition, and countless others.

Work on this project has already been published in the top venues for machine learning (JMLR), computational geometry (SCG, DCG), algorithms (SODA, TOC), and combinatorics (AMS: Contemporary Mathematics).

The algorithms have been implemented and made available publicly. The solutions to instances of hard problems of coordinated motion planning won the international challenge CG:SHOP2021 associated to the conference SCG.

Massive geometric data is increasingly common thanks to the proliferation of ubiquitous data-collecting devices, presenting vexing challenges for algorithmic processing. Our approach to deal with this amount of data is to, given an approximation parameter eps, construct a small-sized sketch S of the input data, then solve the problem on S, and finally extend this solution to a (1+eps)-approximation to the original problem. Our research is divided into three parts, requiring expertise in statistics, computational geometry, learning, combinatorics, and algorithms. First, we consider the combinatorial properties of geometric data that are relevant to build compact sketches. Second, we consider the time and space complexities of constructing accurate sketches of data in high dimensions, based on the combinatorial and geometric understanding. Finally, we show how to use the small sketches in order to improve the accuracy and running time of optimization algorithms.