Group:Lunch Meeting
Title: Space-Efficient Approximation Scheme for Circular Earth Mover Distance
Speaker: Hongyu Yang University
Time: 2012-03-01 12:00-2012-03-01 13:15
Venue: FIT -222


 The Earth Mover Distance (EMD) between two point sets in some metric space is the minimum cost of a bipartite matching between them, where the cost of an edge is the distance between the two endpoints in the space. EMD is an important measure for estimating similarities between objects with quantifiable features and has important applications in several areas including computer vision. The streaming complexity of approximating EMD between point sets in a two-dimensional discretized grid is an important open problem in the streaming community.

In this talk, I will present our recent result on the streaming complexity of EMD on a discretized circle. Computing the EMD in this setting has applications to computer vision and in some sense can be seen as a special case of computing EMD on a discretized grid. We give a $(1+\epsilon)$-approximation streaming algorithm for this problem using $\tilde O(\epsilon^{-3})$ space, for every $0<\epsilon<1$. This is the first constant-factor streaming algorithm for a natural and widely applied EMD model that matches the space bound conjectured by A. McGregor [IITK workshop].

This is joint work with Joshua Brody and Xiaoming Sun.

Short Bio: