[theory students] Theory seminar this Friday!

[Sandeep Silwal <silwal@xxxxxxxxxxx>]

Hi everyone,

We will have our first theory seminar of the semester this Friday 2-3pm in CS 3310. 

I will be presenting on âA Near Linear Time Algorithm for the Chamfer Distance.â

Abstract: 

 I will describe a fast algorithm to approximate the Chamfer distance, a commonly used proxy for the more computationally demanding Earth-Mover (Optimal Transport) Distance. For any two point sets A and B of size n, the Chamfer distance from A to B is defined as CH(A, B) = sum over x in A of d(x, B), where d(x, B) is the minimum distance from x to any point in B. In other words, it is the sum of nearest neighbor distances from A to B. The Chamfer distance is a popular measure of dissimilarity between point clouds, used in many machine learning, computer vision, and graphics applications, and admits a straightforward O(n^2)-time brute force algorithm. However, the quadratic dependence on n in the running time makes the naive approach intractable for large datasets. I will present a (1+epsilon)-approximate algorithm for estimating the Chamfer distance with a near-linear running time. Our experiments demonstrate that it is both accurate and fast on large high-dimensional datasets.

Please let me know if you are interested in giving a talk at some point in the semester (students are welcome as well!).

Next week Manolis will be giving a talk.

This is a one time announcement and all future communications will be done through the theory-seminar mailing list (I promise :) ). Please sign up at https://lists.cs.wisc.edu/mailman/listinfo/theory-seminar if you are interested. 

Best,

Sandeep