Ensimag Rubrique Formation 2022

Optimal Transport: theory, applications and numerical methods (in English) - 5MMTO

  • Number of hours

    • Lectures 36.0
    • Projects -
    • Tutorials -
    • Internship -
    • Laboratory works -
    • Written tests -

    ECTS

    ECTS 3.0

Goal(s)

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.

Responsible(s)

Emmanuel MAITRE

Content(s)

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.

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.

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, denoising, inpainting and interpolation, the latter issue being dealt with by a so-called dynamic formulation of optimal transport.

Prerequisites

Functional analysis and differential calculus

Test

NORMAL SESSION: Written exam (3H, grade Ea)
SECOND SESSION : Written exam (3H, grade Eb)

N1 = Ea
N2 = max(N1,Eb)

Calendar

The course exists in the following branches:

  • Curriculum - Math. Modelling, Image & Simulation - Semester 9
see the course schedule for 2023-2024

Additional Information

Course ID : 5MMTO
Course language(s): FR

The course is attached to the following structures:

You can find this course among all other courses.

Bibliography

C. Villani, Topics in optimal transportation, Graduate Studies in Mathematics, Vol. 50, AMS (2003)
F. Santambroggio, Optimal transport for applied mathematicians, Birkhauser (2015)
Q. Mérigot and B. Thibert, Optimal transport, discretization and algorithms, https://arxiv.org/abs/2003.00855
S. Osher & R. Fedkiw : Level Set Methods and Dynamics Implicit Surfaces, Springer
L.C. Evans, Partial Differential Equations and Monge-Kantorovich Mass Transfer, Notes de
cours sur http://math.berkeley.edu/~evans/