A FAST ALGORITHM FOR Earth Mover’s distance BASED ON OPTIMAL TRANSPORT AND L1 TYPE REGULARIZATION

When
Start: 02/06/2017 - 4:15pm
End  : 02/06/2017 - 5:15pm

Category
Applied Math Seminar

Speaker
Wuchen Li (UCLA)

Abstract

We propose a new algorithm to approximate the Earth Mover's distance (EMD). The main idea is motivated by the theory of optimal transport, in which EMD can be reformulated as a familiar L1 type minimization. We use a regularization which gives us a unique solution for this L1 type problem. The new regularized minimization is very similar to problems which have been solved in the fields of compressed sensing and image processing, where several fast methods are available. In this talk, we adopt a primal-dual algorithm designed there, which uses very simple updates at each iteration and is shown to converge very rapidly. Several numerical examples are provided. This presentation is based on a joint work with Wilfrid Gangbo, Stanley Osher and Penghang Yin.

Where
Emmy Noether Rm Millikan 1021 Pomona College