|
SEMINARS |
PreMoLab Seminar
|
|||
|
Efficient optimal transport in 1D: not as trivial as it may seem A. N. Sobolevski A. A. Kharkevich Institute for Information Transmission Problems, Russian Academy of Sciences, Moscow |
|||
Abstract: We consider two problems of optimal transportation in 1D: (i) optimal matching of two measures on the circle with the cost c(x, y) of matching two points x,y that has a certain convexity property (the Monge condition), and (ii) optimal matching on the line for a concave-type cost satisfying an opposite condition. An optimal matching algorithm in the first case is based on a construction inspired by the weak KAM theory, which reveals a particular convex structure of this problem. In the second case, an algorithm employs a non-obvious submodularity structure. Applications to image processing are discussed. This is a joint work with Julie Delon (Télécom Paris) and Julien Salomon (Université Paris-Dauphine/CEREMADE). |