Algorithms for Geometric Data Analysis

April 3, 2017 - 11:15am to 12:15pm
Duke University
Keller 3-125
Ravi Janardan
Abstract: Rapid advances in sensing technologies and the increasing ubiquity of computing in peoples' lives have led to new opportunities and challenges in the management and analysis of data. Many data sets, such as GPS traces of vehicles, are inherently geometric, while many other kinds of data, such as color histograms of images, are best represented in a geometric space. Therefore, geometric algorithms are needed to handle a variety of problems in data analysis, including computing useful representations, computing maps between data sets, answering queries, and parallel processing of data. This talk will discuss a few of these problems, with an emphasis on the problem of computing maps between data sets.

We will discuss two variants of the problem of computing maps between data sets. First, we will describe a near-linear time approximation algorithm for computing dynamic time warping maps between point sequences, a central problem in the analysis of trajectories and other curves. Next, we will describe fast approximation algorithms for computing transportation maps, a widely used method for comparing and relating two distributions. In both cases our goal is to develop simple, fast, hopefully near-linear-time approximation algorithms. We will conclude the talk by briefly discussing recent algorithms for a few other geometric data-analysis problems as well as mentioning some of the directions of future research in this area.

Bio: Kyle Fox is a postdoctoral associate at Duke University. He obtained his Ph.D. from the University of Illinois at Urbana-Champaign in 2013, and then completed a postdoctoral fellowship at the Institute for Computational and Experimental Research in Mathematics at Brown University before coming to Duke. His research interests lie primarily in algorithms, including geometric algorithms, computational topology, combinatorial optimization, and their applications to data analysis. He was a recipient of the Department of Energy Office of Science Graduate Fellowship and a winner of the C. W. Gear Outstanding Graduate Student award while at the University of Illinois.