Optimal transport in structured domains : algorithms and applications

Optimal transport provides a powerful mathematical framework for comparing probability distributions, and has found successful application in various problems in machine learning, including point cloud matching, generative modeling, and document comparison. However, some important limitations curtail its broader applicability. In many applications there is often additional structural information that is not captured by the classic formulation of the problem. This information can range from explicit tree and graph-like structure, to global structural invariances. Failure to fully model this structure can hinder–if not preclude–the use of optimal transport-based approaches. This thesis presents several extensions of the optimal transport problem to incorporate structural information. First, a non-linear generalization of the cost objective based on submodularity is proposed.