Scalable Unbalanced Optimal Transport by Slicing

by Kimia Nadjahi

Monday Nov 4, 2024, 11:00 AM → 12:00 PM Europe/Paris

1013 (Université Paris-Cité (campus Grands Moulins))

Substantial advances have been made in designing optimal transport (OT) variants which are either computationally and statistically more efficient or robust. Among them, sliced OT distances have been extensively used to mitigate the cubic algorithmic complexity and curse of dimensionality of OT. In parallel, unbalanced OT was designed to allow comparisons of more general positive measures, while being robust to outliers. In this talk, we bridge the gap between those two concepts and develop a general framework for efficiently comparing positive measures. We formulate two different versions of "sliced unbalanced OT" and study the associated topology and statistical properties. We then develop a GPU-friendly Frank-Wolfe algorithm to compute the two corresponding loss functions. The resulting methodology is modular, as it encompasses and extends prior related work, and brings the cubical computational complexity down to almost linear O(n log(n)) when comparing two discrete measures supported on n points.  We finally conduct an empirical analysis of our methodology on both synthetic and real datasets, to illustrate its computational efficiency, relevance and applicability to real-world scenarios, including color transfer and barycenters of geophysical data.

 

Reference : "Slicing Unbalanced Optimal Transport", Clément Bonet, Kimia Nadjahi, Thibault Séjourné, Kilian Fatras, Nicolas Courty (2024, preprint), https://arxiv.org/abs/2306.07176