Iterative Markovian Fitting

Below is a clear, concise explanation of Iterative Markovian Fitting (IMF) — what it is, why it appears in optimal transport / Schrödinger bridge problems, and how it relates to IPF.

Below is clean, implementation-ready pseudocode for Iterative Markovian Fitting (IMF) for the Schrödinger Bridge in discrete time with a reference Markov chain. This is the standard algorithm used in entropic optimal transport over paths and in discrete Schrödinger bridges.

# Inputs:
#   R[t][x,y] : reference transition matrix at time t (size n×n)
#   mu0[x]    : initial distribution
#   muT[x]    : final distribution
#   T         : time horizon

initialize g_t[x] = 1 for all t = 0..T, x = 1..n
initialize f_t[x] = 1 for all t = 0..T, x = 1..n

repeat until convergence:

    # ----- BACKWARD PASS -----
    # enforce final marginal: f_T * g_T = mu_T
    for x in 1..n:
        f[T][x] = muT[x] / g[T][x]

    # compute backward Schrödinger potentials
    for t = T-1 down to 0:
        for x in 1..n:
            f[t][x] = sum_y R[t][x,y] * f[t+1][y]

    # ----- FORWARD PASS -----
    # enforce initial marginal: f_0 * g_0 = mu_0
    for x in 1..n:
        g[0][x] = mu0[x] / f[0][x]

    # compute forward Schrödinger potentials
    for t = 0 to T-1:
        for y in 1..n:
            g[t+1][y] = sum_x R[t][x,y] * g[t][x]

until convergence

# Output:
#   P_t(x,y) = R_t(x,y) * g[t+1][y] / g[t][x]

I’ll give a focused, math-first explanation of Diffusion Schrödinger Bridge Matching (DSBM): what problem it solves, the key theoretical identities, the iterative projection viewpoint (IMF), how the two matching steps (flow/Markovian and bridge/reciprocal) are computed in practice, and the concrete losses / algorithm used to fit neural drifts. I’ll cite the paper(s) as I go so you can jump to the source for proofs and implementation details