Optimal Multimarginal Schrödinger Bridge: Minimum Spanning Tree over Measure-valued Vertices
The Multimarginal Schrödinger Bridge (MSB) finds the optimal coupling among a collection of random vectors with known statistics and a known correlation structure. In the MSB formulation, this correlation structure is specified \emph{a priori} as an undirected connected graph with measure-valued vertices. In this work, we formulate and solve the problem of finding the optimal MSB in the sense we seek the optimal coupling over all possible graph structures. We find that computing the optimal MSB amounts to solving the minimum spanning tree problem over measure-valued vertices. We show that the resulting problem can be solved in two steps. The first step constructs a complete graph with edge weight equal to a sum of the optimal value of the corresponding bimarginal SB and the entropies of the endpoints. The second step solves a standard minimum spanning tree problem over that complete weighted graph. Numerical experiments illustrate the proposed solution.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Tree-Based Diffusion Schrödinger Bridge with Applications to Wasserstein Barycenters
Multi-marginal Optimal Transport (mOT), a generalization of OT, aims at minimizing the integral of a cost function with respect to a distribution with some prescribed marginals. In this paper, we consider an entropic ver…
Path Structured Multimarginal Schrödinger Bridge for Probabilistic Learning of Hardware Resource Usage by Control Software
The solution of the path structured multimarginal Schr\"{o}dinger bridge problem (MSBP) is the most-likely measure-valued trajectory consistent with a sequence of observed probability measures or distributional snapshots…
Model Predictive ControlNeural Schrödinger Bridge with Sinkhorn Losses: Application to Data-driven Minimum Effort Control of Colloidal Self-assembly
We show that the minimum effort control of colloidal self-assembly can be naturally formulated in the order-parameter space as a generalized Schr\"{o}dinger bridge problem -- a class of fixed-horizon stochastic optimal c…
Stochastic Learning of Computational Resource Usage as Graph Structured Multimarginal Schrödinger Bridge
We propose to learn the time-varying stochastic computational resource usage of software as a graph structured Schr\"odinger bridge problem. In general, learning the computational resource usage from data is challenging …
CPUSchrödinger Bridge with Quadratic State Cost is Exactly Solvable
Schr\"{o}dinger bridge is a diffusion process that steers a given distribution to another in a prescribed time while minimizing the effort to do so. It can be seen as the stochastic dynamical version of the optimal mass …