UE Optimal transport: theory, applications and related numerical methods

The goal of this course is to present a wide range of recent numerical methods and algorithms that find applications in various fields. More precisely, the course will focus on optimal transport algorithms, proximal methods and level set methods – the leading application of these being image analysis.

Optimal transport is an important field of mathematics that was originally introduced in the 1700’s by the French mathematician and engineer Gaspard Monge to answer the following concrete question: what is the cheapest way of sending a pile of sand into a hole, knowing the cost of transportation of each sand grain of the pile to a possible target location? This problem gave the birth of the theory of optimal transport. This theory has connections with PDEs, geometry and probability and has been used in many fields such as computer vision, economy, non-imaging optics… In the last 15 years, this problem has been extensively studied from a computational point of view and different efficient algorithms have been proposed.

In this course, we will provide an introduction to the optimal transport theory and the analysis of several algorithms dedicated to the discrete case (i.e. when the source and target measures are discrete), such as Auction’s algorithm and Sinkorn algorithm. We will also study the semi-discrete setting that corresponds to transporting a continuous measure to a discrete one and we will analyze Oliker-Prüssner algorithm as well as a Newton algorithm.

We will also consider some numerical methods which have wide applications in several modeling fields as the Level Set method to capture interfaces, primal dual methods, with main application in this course to image analysis : active contours, deblurring, demonising, inpainting and interpolation, the latter issue being dealt with by a so-called dynamic formulation of optimal transport.