Optimal transport and applications
Abstract:
Optimal transport is a mathematical discipline with numerous interesting applications. While traditionally it has found applications in civil engineering (e.g. optimal mass transport) and economics (e.g. traveling salesman problems), optimal transport modeling techniques have recently begun being widely adopted in numerous applications including: signal/image processing, machine learning, control, data science and others. This course will introduce students to the mathematics of optimal transport and its modern applications in signal/image processing and machine learning. Specifically, we will describe both the Monge & Kantorovich formulations for the optimal transport problem, solution methods, Wasserstein distances and geometry. We will also describe the concept of transport embeddings, representations, and transforms using linearized optimal transport. Finally we will describe applications of this theory to problems related to data classification, signal estimation and image modeling. Results using real data, together with software, will be demonstrated.
Meetings: Tuesdays, 4-6:20 pm, MR 5 1041
Instructors: Gustavo K. Rohde (gustavo@virginia.edu), Ivan V. Medri (pzr7pr@virginia.edu)
Office hours: Wednesdays 13:30-4:30 hs, MR4 1116A (GKR), TBD (IVM) Mondays 14:00-16:00 hs, MR4 1181
Content Overview
1. Optimal transport theory:
o measures, transport maps/plans, push forward, Monge and Kantorovich optimal transport, static & dynamic formulations, Wasserstein distances, geometry, sliced Wasserstein distances
2. Numerical methods:
o Sorting, linear programming solutions, entropic regularization, PDE solutions
3. Transport representations/embeddings:
o Mathematical transforms, linearized optimal transport (LOT), cumulative distribution transform (CDT), signed CDT, Radon CDT, extensions
4. Applications:
o Detection, estimation, classification, inverse problems, transport-based morphometry, system identification, image and signal processing, machine learning
Weakly plan
Week 1 (8/27) Introduction
Organization. Transport phenomena, examples, and data. Course overview
Overleaf: https://www.overleaf.com/read/jqfvpvdhpzpv#810346
Week 2 (9/03) Optimal transport, measure theory
Optimal transport problem, notes
Measures, push forwards, change of variables, probability measures, Notes
Week 2 (9/10) Optimal transport
Measure theory formulation, Monge formulation, Kantorovich formulation, notes
Week 4 (9/17) Optimal transport
convergence of measures, existence, dual problem, notes
Week 5 (9/24) 1D Optimal transport
1D monge formulation, monotonicity, uniqueness, closed form solution, pseudeo inverse, computation, notes
Week 6 (10/01) Discrete OT solvers
Discrete 1d formulation (1D, ND), simplex method, entropy regularization solutions, notes
Week 7 (10/08) Distances, dynamic formulation
Wasserstein distances, dynamic formulation, Brenier's theorem, notes
Week 8 (10/15) Exam 1
Week 9 (10/21) Dynamic formulation, Brenier theorem
Week 10 (10/28) 1D Transport embeddings
Cumulative distribution transform, estimation, classification, notes
Week 11 (11/12) Transport transforms and applications
Week 12 (11/19) Transport transforms and applications Continuation
CDT, applications slides, RCDT, applications slides, Radon transform notes, Linearized optimal transport and transport-based morphometry slides
Week 13 (11/26) Kantorovich problem & Sinkhorn solutions
Existence of Kantorovich Solutions, existence of regularized problem. Sinkhorn derivation, computational aspects