FURI | Summer 2024, Needs Review

Computing the Optimal Transport Map Between Probabilistic Circuits

Data icon, disabled. Four grey bars arranged like a vertical bar chart.

This work presents an algorithm for computing the globally optimal transport map between two probabilistic circuits (PCs) — known as the Wasserstein distance — which provides a natural way of comparing and interpolating PCs. Furthermore, while the complexity of computing this optimal transport map is NP-hard in general, this work shows that imposing small restrictions on the structure of the two PCs allows for computing a transport map that is globally optimal in polynomial time.