A Sinkhorn-type algorithm for sequentially composed optimal transport is shown to converge exponentially in the Hilbert metric and, for two stages, to have near-linear worst-case time in the plan size.
String Diagram of Optimal Transports
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
We present a novel hierarchical framework for optimal transport (OT) using string diagrams, namely string diagrams of optimal transports. This framework reduces complex hierarchical OT problems to standard OT problems, allowing efficient synthesis of optimal hierarchical transportation plans. Our approach uses algebraic compositions of cost matrices to effectively model hierarchical structures. We also study an adversarial situation with multiple choices in the cost matrices, where we present a polynomial-time algorithm for a relaxation of the problem. Experimental results confirm the efficiency and performance advantages of our proposed algorithm over the naive method.
fields
cs.DS 1years
2024 1verdicts
ACCEPT 1representative citing papers
citing papers explorer
-
Sinkhorn Algorithm for Sequentially Composed Optimal Transports
A Sinkhorn-type algorithm for sequentially composed optimal transport is shown to converge exponentially in the Hilbert metric and, for two stages, to have near-linear worst-case time in the plan size.