A novel alternating projection procedure for computing Schrödinger bridges, introduced by Shi et al. (2023). Unlike Iterative Proportional Fitting (IPF) which alternates between marginal constraints, IMF alternates between two distinct projection operations: Markovian projection — finding the Markov process minimizing reverse-KL to a given path measure while preserving all time marginals; and reciprocal projection — replacing the bridge of a process with the reference bridge while keeping the joint endpoint distribution.
A critical advantage over IPF is that both marginal constraints are preserved at every iteration. In contrast, IPF preserves only one marginal at a time, alternating which constraint is satisfied. Convergence of IMF to the unique Schrödinger bridge solution is proved via a Pythagorean theorem for KL divergence on the space of path measures.
Algorithm
- Initialize with coupling Π⁰.
- Markovian projection: Find Markov process M* with drift v*(t,x) = σ²E[∇log Q_{T|t}(X_T|x)|X_t=x].
- Reciprocal projection: Form Π* = M_{0,T} · Q_{|0,T} (replace bridge with reference bridge, keep endpoint distribution).
- Alternate forward/backward to prevent bias accumulation.
- Repeat until convergence.
Key Properties
- Preserves both marginals throughout (unlike IPF)
- Convergence via Pythagorean theorem for KL divergence
- Forward-backward alternation prevents bias accumulation
- DSBM implements IMF via regression losses
- Dual to IPF: structural constraints vs marginal constraints
Extension to GSB
GSBM (Liu et al., 2024) extends the IMF alternating projection framework to the generalized Schrödinger bridge problem. GSBM’s Stage 1 (matching) corresponds to the Markovian projection step of IMF, while Stage 2 (CondSOC) generalizes the reciprocal projection to account for a state cost . When , GSBM reduces exactly to DSBM/IMF. GSBM inherits the forward-backward alternation scheme and the feasibility-preserving property from DSBM.