$\mathbb{E}[V_{\ell}(\mathbf{Y}_{t\wedge\tau_{\ell,k}})]\leq\mathbb{E}[V_{\ell}(\mathbf{Y}_{0})]+\tilde{B}_{\ell}\textstyle{\int_{0}^{t}(1+\mathbb{E}[V_{\ell}(\mathbf{Y}_{s\wedge\tau_{\ell,k}})])\mathrm{d}s}.$
(207)

Hence, using Grönwall’s lemma we get that for any $\ell\in\mathbb{N}$,
$\sup_{k\in\mathbb{N}}\mathbb{E}[V_{\ell}(\mathbf{Y}_{t\wedge\tau_{\ell,k}})]<+\infty$.
Therefore for any $\ell\in\mathbb{N}$,
$((M_{\ell,t\wedge\tau_{k}})_{t\in[0,T]})_{k\in\mathbb{N}}$ is uniformly
integrable and we have that for any $\ell\in\mathbb{N}$,
$(M_{\ell,t})_{t\in[0,T]}$ is a martingale. Therefore we get that for any
$t\in[0,T]$, $\ell\in\mathbb{N}$

$\mathbb{E}[V_{\ell}(\mathbf{Y}_{t})]\leq\mathbb{E}[V_{\ell}(\mathbf{Y}_{0})]+\tilde{B}_{\ell}\textstyle{\int_{0}^{t}(1+\mathbb{E}[V_{\ell}(\mathbf{Y}_{s})]\mathrm{d}s)}.$
(208)

Using Grönwall’s lemma we get that for any $\ell\in\mathbb{N}$ there exist
$\tilde{C}_{\ell}\geq 0$ such that

$N_{T}(\ell)=\sup_{t\in[0,T]}\mathbb{E}[\|\mathbf{Y}_{t}\|^{2\ell}]\leq\tilde{C}_{\ell}\exp[\tilde{B}_{\ell}T].$
(209)

We have that for any $s,t\in[0,T]$

$\textstyle{\mathbf{Y}_{t}=\mathbf{Y}_{s}+\int_{s}^{t}\\{\alpha\mathbf{Y}_{u}+2\nabla\log
p_{T-t}(\mathbf{Y}_{u})\\}\mathrm{d}u+\sqrt{2}\int_{s}^{t}\mathrm{d}\mathbf{B}_{u}}.$
(210)

Using (186) and Cauchy-Schwarz inequality we have for any $s,t\in[0,T]$

$\displaystyle\mathbb{E}[\|\mathbf{Y}_{t}-\mathbf{Y}_{s}\|^{4}]$
$\displaystyle\leq
64(t-s)^{3}\textstyle{\int_{s}^{t}\\{\alpha^{4}\mathbb{E}[\|\mathbf{Y}_{u}\|^{4}]+16\mathbb{E}[\|\nabla\log
p_{T-t}(\mathbf{Y}_{u})\|^{4}]\\}\mathrm{d}u+48\sqrt{2}(t-s)^{2}}$ (211)
$\displaystyle\leq
64(t-s)^{3}\textstyle{\int_{s}^{t}\\{\alpha^{4}\mathbb{E}[\|\mathbf{Y}_{u}\|^{4}]+128B_{1}^{4}(1+\mathbb{E}[\|\mathbf{Y}_{u}\|^{4}])\\}\mathrm{d}u+48\sqrt{2}(t-s)^{2}}$
(212) $\displaystyle\leq
64(\alpha^{4}+128B_{1}^{4})(1+N_{T}(4))(t-s)^{4}+48\sqrt{2}(t-s)^{2}.$ (213)

Combining (209) and (213) in (190) we get that there exist $C_{3}\geq 0$ such
that

$\|\pi_{\infty}(\mathbb{P}^{R})_{T|0}-\pi_{\infty}\mathrm{Q}_{N}\|_{\mathrm{TV}}^{2}\leq
C_{3}\exp[C_{3}T](\bar{\gamma}+\mathtt{M}^{2}),$ (214)

We conclude the proof upon combining (168) and (214) if $\alpha>0$ and (176)
and (214) if $\alpha=0$. ∎

###  C.3 General SGM and links with existing works

In this section we describe a general algorithm for SGM in Section C.3.1 and
show that the formulation (8) encompasses the ones of (Song et al.,, 2021; Ho
et al.,, 2020) in Section C.3.2.

####  C.3.1 General SGM algorithm

We first present a general algorithm to compute approximate reverse dynamics,
i.e. to compute the reverse-time Markov chain associated with the forward
process

$\mathrm{d}\mathbf{X}_{t}=f_{t}(\mathbf{X}_{t})\mathrm{d}t+\sqrt{2}\mathrm{d}\mathbf{B}_{t},\qquad\mathbf{X}_{0}\sim
p_{\textup{data}}.$ (215)

We use the Euler-Maruyama discretization of (215), i.e. let $X_{0}\sim
p_{\textup{data}}$ and for any $k\in\\{0,\dots,N-1\\}$

$X_{k+1}=X_{k}+\gamma_{k+1}f_{k}(X_{k})+\sqrt{2\gamma_{k+1}}Z_{k+1}.$ (216)

In general, we do not have that $p(x_{k}|x_{0})$ is a Gaussian density
contrary to Song and Ermon, (2019); Ho et al., (2020). However, in this case,
we obtain that for any $x\in\mathbb{R}^{d}$,

$\textstyle{p_{k+1}(x)=(4\uppi\gamma_{k+1})^{-d/2}\int_{\mathbb{R}^{d}}p_{k}(\tilde{x})\exp[-\left\|\mathcal{T}_{k+1}(\tilde{x})-x\right\|^{2}/(4\gamma_{k+1})]\mathrm{d}\tilde{x},}$
(217)

with $\mathcal{T}_{k+1}(x)=\tilde{x}+\gamma_{k+1}f_{k}(\tilde{x})$. Therefore,
we get that for any $x\in\mathbb{R}^{d}$

$\textstyle{(2\gamma_{k+1}p_{k+1}(x))\nabla\log
p_{k+1}(x)=\int_{\mathbb{R}^{d}}(\mathcal{T}_{k+1}(\tilde{x})-x)p_{k}(\tilde{x})\exp[-\left\|\mathcal{T}_{k+1}(\tilde{x})-x\right\|^{2}/(4\gamma_{k+1})]\mathrm{d}\tilde{x}}.$
(218)

Hence, we get that for any $x\in\mathbb{R}^{d}$

$\nabla\log
p_{k+1}(x)=\mathbb{E}[\mathcal{T}_{k+1}(X_{k})-X_{k+1}|X_{k+1}=x]/(2\gamma_{k+1})=-(2\gamma_{k+1})^{1/2}\mathbb{E}[Z_{k+1}|X_{k+1}=x].$
(219)

From this formula we derive a regression problem similar to the one of Section
2.1. We obtain Algorithm 2. We highlight a few differences between our
approach and the ones of Song and Ermon, (2019); Ho et al., (2020):

  1. (a)

As emphasized in (219), the regression problem in Algorithm 2 is different
from the one usually considered in SGM which restrict themselves to the
setting $f_{k}(x)=\alpha x$ with $\alpha=0$ (Song and Ermon,, 2019) or
$\alpha>0$ (Ho et al.,, 2020).

  2. (b)

In the present algorithm we do not use any corrector step (Song et al.,, 2021)
at sampling time. Note that the use of a corrector step is only justified in
the context of classical SGM algorithms and not the DSB method introduced in
Section 3.3. This is because, we do not have access to the marginal of the
time-reverse density during the IPF iterations contrary to classical SGMs.

  3. (c)

Finally, we do not present the Exponential Moving Average (EMA) procedure Song
and Ermon, (2020) which is key to prevent the network from oscillating.
Contrary to the corrector step, this technique can easily be incorporated in
Algorithm 2.

Further comments and additional techniques are presented in Appendix I.

Algorithm 2 Generalized score-matching

1: Inputs:  $(b_{k})_{k\in\\{0,\dots,N-1\\}}$ , $N\in\mathbb{N}$ (nb. of
iterations), $M\in\mathbb{N}$ (batch size), $N_{\textup{epochs}}$ (nb. of
epochs), $(\gamma_{k})_{k\in\\{0,\dots,N-1\\}}$ (stepsizes),
$\\{s_{\theta}\,:\;\theta\in\Theta\\}$ (neural network), $\mathrm{opt}$
(optimizer), $p_{\textup{prior}}$ (prior distribution), $\lambda(k)$ (weights)

2: for $n_{\textup{epoch}}=0,\dots,N_{\textup{epoch}}-1$ do

3: for $j\in\\{1,\dots,M\\}$ do

4: $X_{0}^{j}\sim p_{\textup{data}}$

5: for $k\in\\{0,\dots,N-1\\}$ do

6:
$X_{k+1}^{j}=X_{k}^{j}+\gamma_{k+1}f_{k}(X_{k}^{j})+\sqrt{2\gamma_{k+1}}Z_{k+1}^{j}$

7: end for

8: end for

9:
$\widehat{\ell}(\theta)=M^{-1}\sum_{j=1}^{M}\sum_{k=0}^{N-1}\lambda(k)/(2\gamma_{k+1})\sum_{j=1}^{M}\|\sqrt{2\gamma_{k+1}}s_{\theta}(k+1,X_{k+1}^{j})+Z_{k+1}^{j}\|^{2}$

10:
$\theta_{n_{\textup{epoch}}+1}=\mathrm{opt}(\ell,\theta_{n_{\textup{epoch}}})$

11: end for

12: $X_{N}\sim p_{\textup{prior}}$

13: for $k\in\\{N-1,\dots,0\\}$ do

14:
$X_{k}=X_{k+1}+\gamma_{k+1}\\{-f_{k}(X_{k+1})+2s_{\theta_{N_{\textup{epoch}}}}(k+1,X_{k+1})\\}+\sqrt{2\gamma_{k+1}}Z_{k+1}$

15: end for

16: Output:  $X_{0}$

####  C.3.2 Links with existing work

In this section, we show that we can recover the training and sampling
algorithm of Song and Ermon, (2019) and Ho et al., (2020) by reversing
homogeneous diffusions. Note that Song et al., (2021) identified links with
non-homogeneous SDEs. We explicitly characterize the fundamental difference
between the approaches of Song and Ermon, (2019); Ho et al., (2020) by
identifying the two corresponding forward homogeneous processes (Brownian
motion or Ornstein-Ulhenbeck).

##### Brownian motion

First, we show that we can recover the sampling procedure and the loss
function of Song and Ermon, (2019) by reversing a Brownian motion. Assume that
we have

$\mathrm{d}\mathbf{X}_{t}=\sqrt{2}\mathrm{d}\mathbf{B}_{t},\qquad\mathbf{X}_{0}\sim
p_{\textup{data}}.$ (220)

In what follows we define $\\{Y_{k}\\}_{k=0}^{N-1}$ such that
$\\{Y_{k}\\}_{k=0}^{N-1}$ approximates
$\\{\mathbf{X}_{T-t_{k}}\\}_{k=0}^{N-1}$ for a specific sequence of times
$\\{t_{k}\\}_{k=0}^{N-1}\in\left[0,T\right]^{N}$. We recall that the time-
reversal of (220) is associated with the following SDE

$\mathrm{d}\mathbf{Y}_{t}=2\nabla\log
p_{T-t}(\mathbf{Y}_{t})+\sqrt{2}\mathrm{d}\mathbf{B}_{t}.$ (221)

The Euler-Maruyama discretization of (221) yields for any
$k\in\\{0,\dots,N-1\\}$

$\displaystyle\tilde{Y}_{k+1}=\tilde{Y}_{k}+2\gamma_{k+1}\nabla\log
p_{T-t_{k}}(\tilde{Y}_{k})+\sqrt{2\gamma_{k+1}}Z_{k+1}.$ (222)

where $\\{\gamma_{k+1}\\}_{k=0}^{N-1}$ is a sequence of stepsizes and for any
$k\in\\{0,\dots,N\\}$, $t_{k}=\sum_{j=0}^{k-1}\gamma_{j+1}$. A close form for
$\\{\nabla\log p_{T-t_{k}}\\}_{k=0}^{N-1}$ is not available and in practice we
consider

$Y_{k+1}=Y_{k}+2\gamma_{k+1}s_{\theta^{\star}}(T-t_{k},Y_{k})+\sqrt{2\gamma_{k+1}}Z_{k+1},$
(223)

where for any $k\in\\{0,\dots,N-1\\}$, $s_{\theta^{\star}}(T-t_{k},\cdot)$ is
an approximation of $\nabla\log p_{T-t_{k}}$. The sampling procedure (223) is
similar to the one of Song and Ermon, (2019) upon setting (with the notations
of Song and Ermon, (2019)) $T\leftarrow 1$ in (Song and Ermon,, 2019,
Algorithm 1) (no corrector step), $\alpha_{k}/2\leftarrow\gamma_{k}$ and
$\mathbf{s}_{\boldsymbol{\theta}}(\cdot,\sigma_{k+1})\leftarrow
2s_{\theta^{\star}}(T-t_{k},\cdot)$. It remains to show that
$2s_{\theta^{\star}}$ is the solution to the same regression problem as
$\mathbf{s}_{\boldsymbol{\theta}}$ in (Song and Ermon,, 2019, Equation 6).
First, note that for any $t>0$ and $x_{t}\in\mathbb{R}^{d}$ we have

$\textstyle{p_{t}(x_{t})=(4\uppi
t)^{-d/2}\int_{\mathbb{R}^{d}}p_{\textup{data}}(x_{0})\exp[-\left\|x_{t}-x_{0}\right\|^{2}/(4t)]\mathrm{d}x_{0}.}$
(224)

Therefore, we get that for any $t>0$ and $x_{t}\in\mathbb{R}^{d}$

$\textstyle{\nabla\log
p_{t}(x_{t})}\textstyle{=\int_{\mathbb{R}^{d}}(x_{0}-x_{t})/(2t)p_{0|t}(x_{0}|x_{t})\mathrm{d}x_{0}}={\mathbb{E}}[\mathbf{X}_{0}-\mathbf{X}_{t}|\mathbf{X}_{t}=x_{t}]/(2t).$
(225)

Hence, we have that $\theta^{\star}$ satisfies the following regression
problem

$\textstyle{\theta^{\star}=\operatorname*{arg\,min}_{\theta}\sum_{k=0}^{N-1}\lambda(k)\mathbb{E}[\|(\mathbf{X}_{0}-\mathbf{X}_{T-t_{k}})/(T-t_{k})-2s_{\theta}(T-t_{k},\mathbf{X}_{T-t_{k}})\|]}.$
(226)

Note that this loss function is similar to the one of (Song and Ermon,, 2019,
Equation 6) upon letting $\sigma_{k+1}^{2}\leftarrow 2(T-t_{k})$ and
$L\leftarrow N$. Hence, the two recursions approximately define the same
scheme if for any $k\in\\{0,\dots,N-1\\}$,
$\sigma_{1}^{2}-\sigma_{k+1}^{2}\approx(1/2)\sum_{j=0}^{k-1}\alpha_{j+1}$
since $t_{0}=0$ implies $T=(1/2)\sigma_{1}^{2}$. In Song and Ermon, (2019) we
have for any $k\in\\{0,\dots,N-1\\}$,
$\sigma_{k}^{2}=\kappa^{N-k}\sigma_{N}^{2}$ (recall that $N=L$) with
$\kappa>1$. In addition, we have for any $k\in\\{0,\dots,N-1\\}$,
$\alpha_{k}=\varepsilon\sigma_{k}^{2}/\sigma_{N}^{2}$ for some
$\varepsilon>0$. We get that

$\displaystyle(1/2)\textstyle{\sum_{j=0}^{k-1}\alpha_{j+1}}$
$\displaystyle=\textstyle{(\varepsilon/2)\kappa^{N-1}\sum_{j=0}^{k-1}\kappa^{-j}}$
(227)
$\displaystyle=(\varepsilon/2)(\kappa^{N-1}-\kappa^{N-k-1})/(1-\kappa^{-1})$
(228)
$\displaystyle=\varepsilon/(2(1-\kappa^{-1})\sigma_{N}^{2})(\sigma_{1}^{2}-\sigma_{k+1}^{2}).$
(229)

Hence, the two schemes are identical if
$\varepsilon=2(1-\kappa^{-1})\sigma_{N}^{2}$. In practice in Song and Ermon,
(2019) the authors choose $N=10$, $\sigma_{N}=10^{-2}$, $\sigma_{1}=1$ (hence
$\kappa=10^{4/9}$) and $\varepsilon=2\times 10^{-5}$. We have
$2(1-\kappa^{-1})\sigma_{N}^{2}\approx 1.3\times 10^{-4}$ which has one order
of difference with $\varepsilon$.

##### Ornstein-Ulhenbeck

Second, we show that we can recover the sampling procedure and the loss
function of Ho et al., (2020) by reversing an Ornstein-Ulhenbeck process.
Contrary to the previous analysis we do not show a strict equivalence between
the two recursions but instead that our algorithm can be seen as a first order
approximation of the one of Ho et al., (2020).

In this section, we consider the following diffusion

$\mathrm{d}\mathbf{X}_{t}=-\alpha\mathbf{X}_{t}\mathrm{d}t+\sqrt{2}\mathrm{d}\mathbf{B}_{t},\qquad\mathbf{X}_{0}\sim
p_{\textup{data}}.$ (230)

In what follows we define $\\{Y_{k}\\}_{k=0}^{N-1}$ such that
$\\{Y_{k}\\}_{k=0}^{N-1}$ approximates
$\\{\mathbf{X}_{T-t_{k}}\\}_{k=0}^{N-1}$ for a specific sequence of times
$\\{t_{k}\\}_{k=0}^{N-1}\in\left[0,T\right]^{N}$. We recall that the time-
reversal of (230) is associated with the following SDE

$\mathrm{d}\mathbf{Y}_{t}=\\{\alpha\mathbf{Y}_{t}+2\nabla\log
p_{T-t}(\mathbf{Y}_{t})\\}\mathrm{d}t+\sqrt{2}\mathrm{d}\mathbf{B}_{t}.$ (231)

In what follows, we fix $\alpha=1$. The Euler-Maruyama discretization of (231)
yields for any $k\in\\{0,\dots,N-1\\}$

$\displaystyle\tilde{Y}_{k+1}=(1+\gamma_{k+1})\tilde{Y}_{k}+2\gamma_{k+1}\nabla\log
p_{T-t_{k}}(\tilde{Y}_{k})+\sqrt{2\gamma_{k+1}}Z_{k+1}.$ (232)

where $\\{\gamma_{k+1}\\}_{k=0}^{N-1}$ is a sequence of stepsizes and for any
$k\in\\{0,\dots,N-1\\}$, $t_{k}=\sum_{j=0}^{k-1}\gamma_{j+1}$. A close form
for $\\{\nabla\log p_{T-t_{k}}\\}_{k=0}^{N-1}$ is not available and in
practice we consider

$Y_{k+1}=(1+\gamma_{k+1})Y_{k}+2\gamma_{k+1}s_{\theta^{\star}}(T-t_{k},Y_{k})\mathrm{d}t+\sqrt{2\gamma_{k+1}}Z_{k+1}.$
(233)

In (Ho et al.,, 2020, Equation 11) the backward recursion is given for any
$k\in\\{0,\dots,N-1\\}$

$Y_{k+1}=\alpha_{N-k}^{-1/2}(Y_{k}-\beta_{N-k}/(1-\bar{\alpha}_{N-k})^{1/2}\boldsymbol{\epsilon}_{\theta}(Y_{k},T-t_{k}))+\sigma_{N-k}Z_{k+1}.$
(234)

In (234) we set $\sigma_{k}^{2}=\beta_{k}$ as suggested in Ho et al., (2020)
where for any $k\in\\{0,\dots,N-1\\}$

$\displaystyle\sigma_{k+1}^{2}=\beta_{k+1},\quad\alpha_{k+1}=1-\beta_{k+1},\quad\textstyle{\bar{\alpha}_{k+1}=\prod_{i=1}^{k+1}\alpha_{i}.}$
(235)

We consider a first-order expansion of (234) with respect to
$\\{\beta_{k+1}\\}_{k=0}^{N-1}$. We obtain the following recursion for any
$k\in\\{0,\dots,N-1\\}$

$Y_{k+1}=(1+\beta_{N-k}/2)Y_{k}-\beta_{N-k}/(1-\bar{\alpha}_{N-k})^{1/2}\boldsymbol{\epsilon}_{\theta}(Y_{k},T-t_{k})+\sqrt{\beta_{N-k}}Z_{k+1}.$
(236)

This last recursion is equivalent to (233) upon setting $\beta_{N-k}\leftarrow
2\gamma_{k+1}$ and
$-\boldsymbol{\epsilon}_{\theta}(\cdot,T-t_{k})/(1-\bar{\alpha}_{N-k})^{1/2}\leftarrow-
s_{\theta^{\star}}(T-t_{k},\cdot)$. It remains to show that
$s_{\theta^{\star}}$ is the solution to the same regression problem as
$\boldsymbol{\epsilon}_{\theta}/(1-\bar{\alpha}_{N-\cdot})$ in (Ho et al.,,
2020, Equation 12). First, note that for any $t>0$ and
$x_{t}\in\mathbb{R}^{d}$ we have

$\textstyle{p_{t}(x_{t})=(2\uppi\bar{\sigma}_{t}^{2})^{-d/2}\int_{\mathbb{R}^{d}}p_{\textup{data}}(x_{0})\exp[-\left\|x_{t}-c_{t}x_{0}\right\|^{2}/(2\bar{\sigma}_{t}^{2})]\mathrm{d}x_{0}},$
(237)

with

$c_{t}^{2}=\exp[-2t],\qquad\bar{\sigma}_{t}^{2}=1-\exp[-2t].$ (238)

Therefore we get that for any $t\in\left[0,T\right]$ and
$x_{t}\in\mathbb{R}^{d}$

$\displaystyle\nabla\log p_{t}(x_{t})$
$\displaystyle=\textstyle{\int_{\mathbb{R}^{d}}(c_{t}x_{0}-x_{t})p_{\textup{data}}(x_{0})\exp[-\left\|x_{t}-c_{t}x_{0}\right\|^{2}/(2\bar{\sigma}_{t}^{2})]\mathrm{d}x_{0}}$
(239)
$\displaystyle={\mathbb{E}}\left[c_{t}\mathbf{X}_{0}-\mathbf{X}_{t}\middle|\mathbf{X}_{t}=x_{t}\right]/\bar{\sigma}_{t}^{2}=-{\mathbb{E}}\left[\mathbf{Z}\middle|\mathbf{X}_{t}=x_{t}\right]/\bar{\sigma}_{t},$
(240)

where we recall that $\mathbf{X}_{t}$ has the same distribution as
$c_{t}\mathbf{X}_{0}+\bar{\sigma}_{t}\mathbf{Z}$, with $\mathbf{Z}$ a
$d$-dimensional Gaussian random variable with zero mean and identity
covariance matrix. Hence, we have that $\theta^{\star}$ satisfies the
following regression problem

$\textstyle{\theta^{\star}=\operatorname*{arg\,min}_{\theta}\sum_{k=0}^{N-1}\lambda(k)\mathbb{E}[\|\mathbf{Z}/\sigma_{T-t_{k}}+s_{\theta}(T-t_{k},\mathbf{X}_{T-t_{k}})\|]}.$
(241)

Note that we have

$\textstyle{\sum_{i=1}^{N-k}\beta_{i}=\sum_{i=k}^{N-1}\beta_{N-i}=2\sum_{i=k}^{N-1}\gamma_{i+1}=2(T-t_{k}).}$
(242)

Using this result we have for any $k\in\\{0,\dots,N-1\\}$

$\textstyle{1-\bar{\alpha}_{N-k}=1-\exp[-\sum_{i=1}^{N-k}\log(1-\beta_{i})]\approx
1-\exp[-\sum_{i=1}^{N-k}\beta_{i}]\approx\bar{\sigma}_{T-t_{k}}^{2}.}$ (243)

Let $\tilde{\theta}^{\star}$ the minimizer of (Ho et al.,, 2020, Equation 12)
we have

$\displaystyle\tilde{\theta}^{\star}$
$\displaystyle\approx\textstyle{\operatorname*{arg\,min}_{\theta}\sum_{k=0}^{N-1}(2\alpha_{N-k}(1-\alpha_{N-k}))^{-1}\mathbb{E}[\|\mathbf{Z}-\boldsymbol{\epsilon}_{\theta}(\mathbf{X}_{T-t_{k}},T-t_{k})\|^{2}]}$
(244)
$\displaystyle\approx\textstyle{\operatorname*{arg\,min}_{\theta}\sum_{k=0}^{N-1}(2\alpha_{N-k})^{-1}\mathbb{E}[\|\mathbf{Z}/(1-\alpha_{N-k})^{1/2}-\boldsymbol{\epsilon}_{\theta}(\mathbf{X}_{T-t_{k}},T-t_{k})/(1-\alpha_{N-k})^{1/2}\|^{2}]}$
(245)
$\displaystyle\approx\textstyle{\operatorname*{arg\,min}_{\theta}\sum_{k=0}^{N-1}(2\alpha_{N-k})^{-1}\mathbb{E}[\|\mathbf{Z}/\bar{\sigma}_{T-t_{k}}+s_{\theta}(T-t_{k},\mathbf{X}_{T-t_{k}})\|^{2}]}.$
(246)

Hence the two regression problems are approximately the same (for small values
of $\\{\beta_{k+1}\\}_{k=0}^{N-1}$) if we set
$\lambda(k)=(2\alpha_{N-k})^{-1}$.

##  Appendix D Schrödinger bridges with potentials and DSB recursion

In this section, we start by proving an additive formula for the
Kullback–Leibler divergence in Section D.1 following Léonard, 2014a . We
recall the classical IPF formulation using potentials in Section D.2. Then,
Section 3.2 is proved in Section D.3. Finally, we highlight a link between our
formulation and autoencoders in Section D.4.

###  D.1 Additive formula for the Kullback–Leibler divergence

In this section, we prove a formula for the Kullback–Leibler divergence
following the proof of Léonard, 2014a  which extends the result to unbounded
measures defined on the space of right-continuous left-limited functions from
$\left[0,T\right]$. We recall that a Polish space is a complete metric
separable space.

We start with the following disintegration theorem for probability measures.

######  Theorem 3.

Let $(\mathsf{X},\mathcal{X})$ and $(\mathsf{Y},\mathcal{Y})$ be two Polish
spaces. Let $\pi\in\mathscr{P}(\mathsf{X})$ and $\varphi:\
\mathsf{X}\to\mathsf{Y}$ measurable. Then there exists a Markov kernel
$\mathrm{K}^{\pi}_{\varphi}:\ \mathsf{Y}\times\mathcal{X}\to\left[0,1\right]$
such that the following hold:

  1. (a)

For any $y\in\mathsf{Y}$,
$\mathrm{K}^{\pi}_{\varphi}(y,\varphi^{-1}(\\{y\\}))=1$.

  2. (b)

For any $f:\ \mathsf{X}\to\left[0,+\infty\right)$ measurable we have
$\textstyle{\int_{\mathsf{X}}f(x)\mathrm{d}\pi(x)=\int_{\mathsf{Y}}\mathrm{K}^{\pi}_{\varphi}(y,f)\mathrm{d}\pi_{\varphi}(y)}$,

where $\pi_{\varphi}=\varphi_{\\#}\pi$.

###### Proof.

See (Dellacherie and Meyer,, 1988, III-70) for instance. ∎

$\mathrm{K}^{\pi}_{\varphi}$ is called the disintegration of $\pi$ w.r.t.
$\varphi$ and is unique, see (Dellacherie and Meyer,, 1988, III-70). In
particular, for any $\mathsf{X}$-valued random variable $X$ with distribution
$\pi$ we have
${\mathbb{E}}[f(X)|\varphi(X)]=\mathrm{K}^{\pi}_{\varphi}(\varphi(X),f)$. Next
we prove the following proposition, see (Léonard, 2014a, , Proposition A.13)
for an extension to unbounded measures. In what follows, for any $\varphi:\
\mathsf{X}to\mathbb{R}$ measurable we denote $\pi_{\varphi}=\varphi_{\\#}\pi$.

######  Proposition .

Let $(\mathsf{X},\mathcal{X})$ and $(\mathsf{Y},\mathcal{Y})$ be two Polish
spaces. Let $\pi,\mu\in\mathscr{P}(\mathsf{X})$ and $\varphi:\
\mathsf{X}\to\mathsf{Y}$ measurable. Assume that $\pi\ll\mu$. Then the
following holds:

  1. (a)

$\pi_{\varphi}\ll\mu_{\varphi}$

  2. (b)

There exists $\mathsf{A}\in\mathcal{Y}$ with $\pi_{\varphi}(\mathsf{A})=1$
such that for any $y\in\mathsf{A}$,
$\mathrm{K}_{\varphi}^{\pi}(y,\cdot)\ll\mathrm{K}_{\varphi}^{\mu}(y,\cdot)$.

In addition, we have for any $y\in\mathsf{Y}$, $y^{\prime}\in\mathsf{A}$ and
$x\in\mathsf{X}$

$(\mathrm{d}\pi_{\varphi}/\mathrm{d}\mu_{\varphi})(y)=\mathrm{K}^{\mu}_{\varphi}(y,(\mathrm{d}\pi/\mathrm{d}\mu)),\quad(\mathrm{d}\mathrm{K}_{\varphi}^{\pi}(y^{\prime},\cdot)/\mathrm{d}\mathrm{K}_{\varphi}^{\mu}(y^{\prime},\cdot))(x)=(\mathrm{d}\pi/\mathrm{d}\mu)(x)/(\mathrm{d}\pi_{\varphi}/\mathrm{d}\mu_{\varphi})(y^{\prime}).$
(247)

Finally, there exists $\mathsf{C}\in\mathcal{X}$ with $\pi(\mathsf{C})=1$ such
that for any $x\in\mathsf{C}$ we have

$(\mathrm{d}\pi/\mathrm{d}\mu)(x)=(\mathrm{d}\pi_{\varphi}/\mathrm{d}\mu_{\varphi})(\varphi(x))(\mathrm{d}\mathrm{K}_{\varphi}^{\pi}(\varphi(x),\cdot)/\mathrm{d}\mathrm{K}_{\varphi}^{\mu}(\varphi(x),\cdot))(x).$
(248)

###### Proof.

Let $f:\ \mathsf{X}\to\left[0,+\infty\right)$ measurable. Using Theorem 3 we
have

$\displaystyle\pi_{\varphi}[f]$
$\displaystyle=\textstyle{\int_{\mathsf{X}}f(\varphi(x))\mathrm{d}\pi(x)}=\textstyle{\int_{\mathsf{X}}f(\varphi(x))(\mathrm{d}\pi/\mathrm{d}\mu)(x)\mathrm{d}\mu(x)}=\textstyle{\int_{\mathsf{X}}f(y)\mathrm{K}^{\mu}_{\varphi}(y,(\mathrm{d}\pi/\mathrm{d}\mu))\mathrm{d}\mu_{\varphi}(y),}$
(249)

which concludes the first part of the proof. For the second part of the proof,
let
$\mathsf{B}=\\{y\in\mathsf{Y}\,:\;(\mathrm{d}\pi_{\varphi}/\mathrm{d}\mu_{\varphi})(y)=0\\}$.
We have

$\textstyle{0=\int_{\mathsf{Y}}\mathbbm{1}_{\mathsf{B}}(y)(\mathrm{d}\pi_{\varphi}/\mathrm{d}\mu_{\varphi})(y)\mathrm{d}\mu_{\varphi}(y)=\pi_{\varphi}(\mathsf{B}).}$
(250)

Therefore, there exists $\mathsf{A}_{1}\in\mathcal{Y}$ such that
$\pi_{\varphi}(\mathsf{A}_{1})=1$ and for any $y\in\mathsf{A}_{1}$,
$(\mathrm{d}\pi_{\varphi}/\mathrm{d}\mu_{\varphi})(y)>0$. Let $g:\
\mathsf{Y}\to\left[0,+\infty\right)$. Using Theorem 3 we have

$\textstyle{\int_{\mathsf{X}}g(\varphi(x))f(x)\mathrm{d}\pi(x)=\int_{\mathsf{X}}g(\varphi(x))f(x)(\mathrm{d}\pi/\mathrm{d}\mu)(x)\mathrm{d}\mu(x)=\int_{\mathsf{Y}}g(y)\mathrm{K}_{\varphi}^{\mu}(y,f\times(\mathrm{d}\pi/\mathrm{d}\mu))\mathrm{d}\mu_{\varphi}(y).}$
(251)

Similarly, using Theorem 3 we have

$\textstyle{\int_{\mathsf{X}}g(\varphi(x))f(x)\mathrm{d}\pi(x)=\int_{\mathsf{Y}}g(y)\mathrm{K}_{\varphi}^{\pi}(y,f)\mathrm{d}\pi_{\varphi}(y)=\int_{\mathsf{Y}}g(y)\mathrm{K}_{\varphi}^{\pi}(y,f)(\mathrm{d}\pi_{\varphi}/\mathrm{d}\mu_{\varphi})(y)\mathrm{d}\pi_{\varphi}(y).}$
(252)

Hence, we get that there exists $\mathsf{A}_{2}\in\mathcal{Y}$ with
$\mu_{\varphi}(\mathsf{A}_{2})=1$ (hence $\pi_{\varphi}(\mathsf{A}_{2})=1$)
such that for any $y\in\mathsf{A}_{2}$ we have

$\mathrm{K}_{\varphi}^{\pi}(y,f)(\mathrm{d}\pi_{\varphi}/\mathrm{d}\mu_{\varphi})(y)=\mathrm{K}_{\varphi}^{\mu}(y,f\times(\mathrm{d}\pi/\mathrm{d}\mu)).$
(253)

We conclude upon letting $\mathsf{A}=\mathsf{A}_{1}\cap\mathsf{A}_{2}$ and
using the fact that for any $y\in\mathsf{A}$,
$(\mathrm{d}\pi_{\varphi}/\mathrm{d}\mu_{\varphi})(y)>0$. Finally, since
$\pi_{\varphi}(\mathsf{A})=1$ if and only if
$\pi(\varphi^{-1}(\mathsf{A}))=1$, we have for any
$x\in\varphi^{-1}(\mathsf{A})$

$(\mathrm{d}\pi/\mathrm{d}\mu)(x)=(\mathrm{d}\pi_{\varphi}/\mathrm{d}\mu_{\varphi})(\varphi(x))(\mathrm{d}\mathrm{K}_{\varphi}^{\pi}(\varphi(x),\cdot)/\mathrm{d}\mathrm{K}_{\varphi}^{\mu}(\varphi(x),\cdot))(x),$
(254)

which concludes the proof. ∎

We are now ready to state the additive formula.

######  Proposition .

Let $(\mathsf{X},\mathcal{X})$ and $(\mathsf{Y},\mathcal{Y})$ be two Polish
spaces and $\pi,\mu\in\mathscr{P}(\mathsf{X})$ with $\pi\ll\mu$. Then for any
$\varphi:\ \mathsf{X}\to\mathsf{Y}$ we have

$\textstyle{\operatorname{KL}(\pi|\mu)=\operatorname{KL}(\pi_{\varphi}|\mu_{\varphi})+\int_{\mathsf{Y}}\operatorname{KL}(\mathrm{K}^{\pi}_{\varphi}(y,\cdot)|\mathrm{K}^{\mu}_{\varphi}(y,\cdot))\mathrm{d}\pi_{\varphi}(y).}$
(255)

###### Proof.

First assume that
$\int_{\mathsf{X}}\left|\log((\mathrm{d}\pi/\mathrm{d}\mu)(x))\right|\mathrm{d}\pi(x)=+\infty$.
Then, using Section D.1 we have
$\int_{\mathsf{X}}\left|\log((\mathrm{d}\pi_{\varphi}/\mathrm{d}\mu_{\varphi})(\varphi(x)))\right|\mathrm{d}\pi(x)=+\infty$
or
$\int_{\mathsf{X}}\left|\log((\mathrm{d}\mathrm{K}^{\pi}_{\varphi}(\varphi(x),\cdot)/\mathrm{d}\mathrm{K}^{\mu}_{\varphi}(\varphi(x),\cdot))(x))\right|\mathrm{d}\pi(x)=+\infty$,
i.e. either $\operatorname{KL}(\pi_{\varphi}|\mu_{\varphi})=+\infty$ or
$\int_{\mathsf{X}}\operatorname{KL}(\mathrm{K}^{\pi}_{\varphi}(\varphi(x),\cdot)|\mathrm{K}^{\mu}_{\varphi}(\varphi(x),\cdot))\mathrm{d}\pi(x)=+\infty$
using Theorem 3, which concludes the first part of the proof. Second, assume
that
$\int_{\mathsf{X}}\left|\log((\mathrm{d}\pi/\mathrm{d}\mu)(x))\right|\mathrm{d}\pi(x)<+\infty$.
Using Pinsker’s inequality (Bakry et al.,, 2014, Equation 5.2.2) we get that
$\operatorname{KL}(\pi_{\varphi}|\mu_{\varphi})<+\infty$, i.e.
$\int_{\mathsf{X}}\left|\log((\mathrm{d}\pi_{\varphi}/\mathrm{d}\mu_{\varphi})(\varphi(x)))\right|\mathrm{d}\pi(x)<+\infty$.
Hence, we get that
$\int_{\mathsf{X}}\left|\log((\mathrm{d}\mathrm{K}^{\pi}_{\varphi}(\varphi(x),\cdot)/\mathrm{d}\mathrm{K}^{\mu}_{\varphi}(\varphi(x),\cdot))(x))\right|\mathrm{d}\pi(x)<+\infty$.
Therefore we have

$\textstyle{\operatorname{KL}(\pi|\mu)=\operatorname{KL}(\pi_{\varphi}|\mu_{\varphi})+\int_{\mathsf{Y}}\operatorname{KL}(\mathrm{K}^{\pi}_{\varphi}(y,\cdot)|\mathrm{K}^{\mu}_{\varphi}(y,\cdot))\mathrm{d}\pi_{\varphi}(y)}$
(256)

which concludes the proof ∎

We emphasize that in the case where
$\mathsf{X}=\mathbb{R}^{d}\times\mathbb{R}^{d}$, $\varphi=\mathrm{proj}_{0}$
the projection on the first variable and $\pi$, $\mu$ admit densities w.r.t.
the Lebesgue measure denoted $p$ and $q$ such that for any
$x,y\in\mathbb{R}^{d}$, $p(x,y)=p_{0}(x)p_{1|0}(y|x)$ and
$q(x,y)=q_{0}(x)q_{1|0}(y|x)$ then one can avoid using disintegration theory
and Section D.1 can be proved directly.

###  D.2 Iterative Proportional Fitting via potentials

In this section, before recalling the usual definition of the IPF via
potentials we provide a condition under which the IPF sequence is well-defined
which is used throughout Section 3.2.

######  Proposition .

Assume that there exists $\tilde{\pi}\in\mathscr{P}_{N+1}$ such that
$\tilde{\pi}_{0}=p_{\textup{data}}$, $\tilde{\pi}_{N}=p_{\textup{prior}}$ and
$\operatorname{KL}(\tilde{\pi}|\pi^{0})<+\infty$. Then the IPF sequence is
well-defined.

###### Proof.

We prove the existence of the IPF sequence by recursion. First, note that
$\pi^{1}$ is well-defined since $\tilde{\pi}\in\mathscr{P}_{N+1}$ with
$\tilde{\pi}_{N}=p_{\textup{prior}}$ and
$\operatorname{KL}(\tilde{\pi}|\pi^{0})<+\infty$. Second, assume that the
sequence is well-defined up to $n$ with $n\in\mathbb{N}$. Using (Csiszár,,
1975, Theorem 2.2) we have

$\textstyle{\operatorname{KL}(\tilde{\pi}|\pi^{0})=\operatorname{KL}(\tilde{\pi}|\pi^{n})+\sum_{j=0}^{n-1}\operatorname{KL}(\pi^{j+1}|\pi^{j}).}$
(257)

Hence $\operatorname{KL}(\tilde{\pi}|\pi^{n})<+\infty$. Using that
$\tilde{\pi}_{0}=p_{\textup{data}}$ if $n$ is odd and that
$\tilde{\pi}_{N}=p_{\textup{prior}}$ if $n$ is even, we get that $\pi^{n+1}$
is well-defined, which concludes the proof. ∎

We now introduce the IPF using potentials. This construction is not new and
can be found in Bernton et al., (2019); Chen et al., (2016); Chen et al.,
2021b ; Pavon et al., (2021); Peyré and Cuturi, (2019) for instance (in
continuous state spaces). In discrete settings the recursion can be found in
the following earlier works Kruithof, (1937); Deming and Stephan, (1940);
Fortet, (1940); Sinkhorn and Knopp, (1967); Kullback, (1968); Ruschendorf et
al., (1995). The IPF is defined by the following recursion $\pi^{0}=p$ given
in (1) and for $n\geq 0$

$\displaystyle\pi^{2n+1}=\operatorname*{arg\,min}\left\\{\operatorname{KL}(\pi|\pi^{2n})\,:\;\pi\in\mathscr{P}_{N+1},\
\pi_{N}=p_{\textup{prior}}\right\\},$ (258)
$\displaystyle\pi^{2n+2}=\operatorname*{arg\,min}\left\\{\operatorname{KL}(\pi|\pi^{2n+1})\,:\;\pi\in\mathscr{P}_{N+1},\
\pi_{0}=p_{\textup{data}}\right\\}.$ (259)

In the classical IPF presentation we obtain under mild assumptions that
$\pi^{2n+1}$ admits a density $q^{n}$ w.r.t the Lebesgue measure and that
$\pi^{2n}$ admits a density $p^{n}$ w.r.t the Lebesgue measure, given by the
following expressions

$\displaystyle\textstyle{q^{n}(x_{0:N})=p_{\textup{data}}^{n}(x_{0})\prod_{k=0}^{N-1}p^{n+1}_{k+1|k}(x_{k+1}|x_{k})},$
(260)
$\displaystyle\textstyle{p^{n+1}(x_{0:N})=p_{\textup{data}}(x_{0})\prod_{k=0}^{N-1}p^{n+1}_{k+1|k}(x_{k+1}|x_{k})},$
(261)

where $(p_{\textup{data}}^{n}(x_{0}))_{n\in\mathbb{N}}$ and
$(p^{n}_{k+1|k}(x_{k+1}|x_{k}))_{n\in\mathbb{N}}$ are densities which are
iteratively computed, with $p^{0}_{k+1|k}=p_{k+1|k}$.

In the context of generative modelling the derivation (260) is not useful
because it does not provide a generative model, i.e. a probabilistic
transition from $p_{\textup{prior}}$ to $p_{\textup{data}}$ but instead
defines a transition from $p_{\textup{data}}$ to $p_{\textup{prior}}$.
Therefore, in this section only, we reverse the roles of $p_{\textup{prior}}$
and $p_{\textup{data}}$ and consider a reference density $\bar{p}$ such that
for any $x_{0:N}\in\mathcal{X}$ we have

$\textstyle{\bar{p}(x_{0:N})=p_{\textup{prior}}(x_{0})\prod_{k=0}^{N-1}\bar{p}_{k+1|k}(x_{k+1}|x_{k}).}$
(262)

Then, we consider the following recursion $\pi^{0}=\bar{p}$ given in (262) and
for $n\in\mathbb{N}$

$\displaystyle\pi^{2n+1}=\operatorname*{arg\,min}\left\\{\operatorname{KL}(\pi|\pi^{2n})\,:\;\pi\in\mathscr{P}_{N+1},\
\pi_{N}=p_{\textup{data}}\right\\},$ (263)
$\displaystyle\pi^{2n+2}=\operatorname*{arg\,min}\left\\{\operatorname{KL}(\pi|\pi^{2n+1})\,:\;\pi\in\mathscr{P}_{N+1},\
\pi_{0}=p_{\textup{prior}}\right\\}.$ (264)

Again, we emphasize that the roles of $p_{\textup{prior}}$ and
$p_{\textup{data}}$ are exchanged in this formulation. Using the classical IPF
presentation we obtain the following expressions under mild assumptions

$\displaystyle\textstyle{\bar{q}^{n}(x_{0:N})=p_{\textup{prior}}^{n}(x_{0})\prod_{k=0}^{N-1}\bar{p}^{n+1}(x_{k+1}|x_{k}),}$
(265)
$\displaystyle\textstyle{\bar{p}^{n+1}(x_{0:N})=p_{\textup{prior}}(x_{0})\prod_{k=0}^{N-1}\bar{p}^{n+1}(x_{k+1}|x_{k}).}$
(266)

In this case, we get that $\pi^{2n+1}$ (approximately) defines a generative
model for large values of $n\in\mathbb{N}$ since it provides a transition from
to $p_{\textup{prior}}$ to (approximately) $p_{\textup{data}}$. In the
following proposition we give the precise statement corresponding to (265). We
assume that $\bar{p}^{0}=\bar{p}$.

######  Proposition .

Assume that $\operatorname{KL}(p_{\textup{prior}}\otimes
p_{\textup{data}}|\bar{p}_{0,N})<+\infty$. Then $(\pi^{n})_{n\in\mathbb{N}}$
given by (263) is well-defined and for any $n\in\mathbb{N}$ we have that
$\pi^{2n+1}$ and $\pi^{2n+2}$ admit a density w.r.t. the Lebesgue measures
denoted $\bar{q}^{n}$ and $\bar{p}^{n+1}$. In addition, we have for any
$n\in\mathbb{N}$ and $x_{0:N}\in\mathcal{X}$

$\displaystyle\textstyle{\bar{q}^{n}(x_{0:N})=p_{\textup{prior}}^{n}(x_{0})\prod_{k=0}^{N-1}\bar{p}^{n+1}(x_{k+1}|x_{k})},$
(267)
$\displaystyle\textstyle{\bar{p}^{n+1}(x_{0:N})=p_{\textup{prior}}(x_{0})\prod_{k=0}^{N-1}\bar{p}^{n+1}(x_{k+1}|x_{k})},$
(268)

where for any $n\in\mathbb{N}$ we have for any $x_{0:N}\in\mathcal{X}$ and
$k\in\\{0,\dots,N-1\\}$

$p_{\textup{prior}}^{n}(x_{0})=\psi_{0}^{n}(x_{0})p_{\textup{prior}}(x_{0}),\quad\bar{p}^{n+1}(x_{k+1}|x_{k})=\bar{p}^{n}(x_{k+1}|x_{k})\psi_{k+1}^{n}(x_{k+1})/\psi_{k}^{n}(x_{k}),$
(269)

with

$\psi_{N}^{n}(x_{N})=p_{\textup{data}}(x_{N})/\bar{p}_{N}^{n}(x_{N}),\quad\textstyle{\psi_{k}^{n}(x_{k})=\int_{\mathbb{R}^{d}}\psi_{k+1}^{n}(x_{k+1})\bar{p}^{n}(x_{k+1}|x_{k})\mathrm{d}x_{k+1}.}$
(270)

###### Proof.

Let $\tilde{\pi}=(p_{\textup{prior}}\otimes p_{\textup{data}})\bar{p}_{|0,N}$.
Using Section D.1 we get that
$\operatorname{KL}(\tilde{\pi}|\bar{p})=\operatorname{KL}(p_{\textup{prior}}\otimes
p_{\textup{data}}|\bar{p}_{0,N})<+\infty$. Using Section D.2 the IPF sequence
is well-defined. In addition, using (Csiszár,, 1975, Theorem 3.1) for any
$n\in\mathbb{N}$ there exists $\psi_{N}^{n}:\
\mathbb{R}^{d}\to\left[0,+\infty\right)$ such that for any
$x_{0:N}\in\mathsf{A}$ with $\tilde{\pi}(\mathsf{A})=1$ we have

$\bar{q}^{n}(x_{0:N})=\bar{p}^{n}(x_{0:N})\psi_{N}^{n}(x_{N}).$ (271)

Since $\tilde{\pi}$ is equivalent to the Lebesgue measure we get that for any
$x_{0:N}\in\mathbb{R}^{d}$

$\bar{q}^{n}(x_{0:N})=\bar{p}^{n}(x_{0:N})\psi_{N}^{n}(x_{N}).$ (272)

Let $n\in\mathbb{N}$. We have for any $x_{N}\in\mathbb{R}^{d}$,
$p_{\textup{data}}(x_{N})=\bar{q}^{n}(x_{N})=\bar{p}^{n}_{N}(x_{N})\psi_{N}^{n}(x_{N})$.
Hence, we get that for any $N\in\mathbb{N}$,
$\psi_{N}^{n}(x_{N})=p_{\textup{data}}(x_{N})/\bar{p}^{n}_{N}(x_{N})$. For any
$x_{0:N}\in\mathcal{X}$ and $k\in\\{0,\dots,N-1\\}$ let

$\textstyle{\psi_{k}^{n}(x_{k})=\int_{\mathbb{R}^{d}}\psi_{k+1}^{n}(x_{k+1})\bar{p}^{n}(x_{k+1}|x_{k})\mathrm{d}x_{k+1}.}$
(273)

We obtain that for any $x_{0:N}\in\mathcal{X}$

$\textstyle{\bar{q}^{n}(x_{0:N})=p_{\textup{prior}}(x_{0})\psi_{0}(x_{0})\prod_{k=0}^{N-1}(\bar{p}^{n}(x_{k+1}|x_{k})\psi_{k+1}(x_{k+1})/\psi_{k}(x_{k})).}$
(274)

Hence, we get that for any $x_{0:N}\in\mathcal{X}$,
$\bar{q}^{n}(x_{0})=p_{\textup{prior}}^{n}(x_{0})\prod_{k=0}^{N-1}\bar{p}^{n+1}(x_{k+1}|x_{k})$.
Using Section D.1 we get that for any $x_{0:N}\in\mathcal{X}$,
$\bar{p}^{n+1}(x_{0})=p_{\textup{prior}}(x_{0})\prod_{k=0}^{N-1}\bar{p}^{n+1}(x_{k+1}|x_{k})$,
which concludes the proof. ∎

The previous expression is not symmetric and the IPF iterations appear as a
policy refinement of the original forward dynamic $\bar{p}$. In the next
proposition we present another potential formulation of the IPF iterations
which is symmetric.

######  Proposition .

Assume that $\operatorname{KL}(p_{\textup{prior}}\otimes
p_{\textup{data}}|q_{0,N})<+\infty$. Then $(\pi^{n})_{n\in\mathbb{N}}$ given
by (263) is well-defined and for any $n\in\mathbb{N}$ we have that
$\pi^{2n+1}$ and $\pi^{2n+2}$ admit a density w.r.t. the Lebesgue measures
denoted $\bar{q}^{n}$ and $\bar{p}^{n+1}$. In addition, we have for any
$n\in\mathbb{N}$ and $x_{0:N}\in\mathcal{X}$

$\displaystyle\textstyle{\bar{q}^{n}(x_{0:N})=\varphi_{0}^{n}(x_{0})\prod_{k=0}^{N-1}\bar{p}(x_{k+1}|x_{k})\psi_{N}^{n}(x_{N})},$
(275)
$\displaystyle\textstyle{\bar{p}^{n+1}(x_{0:N})=\varphi_{0}^{n+1}(x_{0})\prod_{k=0}^{N-1}\bar{p}(x_{k+1}|x_{k})\psi_{N}^{n}(x_{N})},$
(276)

where for any $n\in\mathbb{N}$ we have for any $x_{0:N}\in\mathcal{X}$ and
$k\in\\{0,\dots,N-1\\}$

$\displaystyle\psi_{N}^{n}(x_{N})=p_{\textup{data}}(x_{N})/\varphi_{N}^{n}(x_{N}),\quad\textstyle{\psi_{k}^{n}(x_{k})=\int_{\mathbb{R}^{d}}\psi_{k+1}^{n}(x_{k+1})\bar{p}(x_{k+1}|x_{k})\mathrm{d}x_{k+1},}$
(277)
$\displaystyle\varphi_{0}^{n+1}(x_{0})=p_{\textup{prior}}(x_{0})/\psi_{0}^{n}(x_{0}),\quad\textstyle{\varphi_{k+1}^{n+1}(x_{k+1})=\int_{\mathbb{R}^{d}}\varphi_{k}^{n+1}(x_{k})\bar{p}(x_{k+1}|x_{k})\mathrm{d}x_{k},}$
(278)

and $\varphi_{0}^{0}=p_{\textup{prior}}$ and $\psi_{N}^{-1}=1$.

###### Proof.

Let $\tilde{\pi}=(p_{\textup{prior}}\otimes p_{\textup{data}})q_{|0,N}$. Using
Section D.1 we get that
$\operatorname{KL}(\tilde{\pi}|q)=\operatorname{KL}(p_{\textup{prior}}\otimes
p_{\textup{data}}|p_{0,N})<+\infty$. Using Section D.2 the IPF sequence is
well-defined. In addition, using (Csiszár,, 1975, Theorem 3.1) for any
$n\in\mathbb{N}$ there exists $\psi_{N}^{n}:\
\mathbb{R}^{d}\to\left[0,+\infty\right)$ such that for any
$x_{0:N}\in\mathsf{A}$ with $\tilde{\pi}(\mathsf{A})=1$ we have

$\bar{q}^{n}(x_{0:N})=\bar{p}^{n}(x_{0:N})\tilde{\psi}_{N}^{n}(x_{N}),\qquad\bar{p}^{n+1}(x_{0:N})=\bar{q}^{n}(x_{0:N})\tilde{\varphi}_{0}^{n}(x_{0}).$
(279)

Since $\tilde{\pi}$ is equivalent to the Lebesgue measure we get that for any
$x_{0:N}\in\mathbb{R}^{d}$

$\bar{q}^{n}(x_{0:N})=\bar{p}^{n}(x_{0:N})\tilde{\psi}_{N}^{n}(x_{N}),\qquad\bar{p}^{n+1}(x_{0:N})=\bar{q}^{n}(x_{0:N})\tilde{\varphi}_{0}^{n}(x_{0}).$
(280)

For any $n\in\mathbb{N}$, let
$\psi_{N}^{n}=\psi_{N}^{n-1}\tilde{\psi}^{n}_{N}$ and
$\varphi_{0}^{n+1}=\varphi_{0}^{n}\tilde{\varphi}_{0}^{n}$. By recursion, we
get that for any $n\in\mathbb{N}$ and $x_{0:N}\in\mathcal{X}$

$\displaystyle\textstyle{\bar{q}^{n}(x_{0:N})=\varphi_{0}^{n}(x_{0})\prod_{k=0}^{N-1}\bar{p}(x_{k+1}|x_{k})\psi_{N}^{n}(x_{N})},$
(281)
$\displaystyle\textstyle{\bar{p}^{n+1}(x_{0:N})=\varphi_{0}^{n+1}(x_{0})\prod_{k=0}^{N-1}\bar{p}(x_{k+1}|x_{k})\psi_{N}^{n}(x_{N}).}$
(282)

Let $n\in\mathbb{N}$. For any $x_{N}\in\mathbb{R}^{d}$ we have

$\bar{q}^{n}_{N}(x_{N})=p_{\textup{data}}(x_{N})=\bar{p}^{n}_{N}(x_{N})\tilde{\psi}_{N}^{n}(x_{n}).$
(283)

In addition, for any $k\in\\{0,\dots,N-1\\}$ and $x_{0:N}\in\mathcal{X}$ we
define
$\varphi_{k+1}^{n+1}(x_{k+1})=\int_{\mathbb{R}^{d}}\varphi_{k}^{n+1}(x_{k})\bar{p}(x_{k+1}|x_{k})\mathrm{d}x_{k}$.
We have for any $x_{N}\in\mathbb{R}^{d}$,
$\bar{p}_{N}^{n}(x_{N})=\varphi_{N}^{n}(x_{N})\psi_{N}^{n-1}(x_{n})$.
Combining this result with (283) we get that for any $x_{N}\in\mathbb{R}^{d}$

$\psi_{N}^{n}(x_{N})=p_{\textup{data}}(x_{N})/\varphi^{n}_{N}(x_{N}).$ (284)

Similarly, we get that for any $x_{0}\in\mathbb{R}^{d}$,
$\varphi_{0}^{n+1}(x_{0})=p_{\textup{prior}}(x_{0})/\psi_{0}^{n}(x_{0})$,
which concludes the proof. ∎

###  D.3 Proof of Section 3.2

Let $\tilde{\pi}=(p_{\textup{prior}}\otimes p_{\textup{data}})p_{|0,N}$. Using
Section D.1 we get that
$\operatorname{KL}(\tilde{\pi}|p)=\operatorname{KL}(p_{\textup{prior}}\otimes
p_{\textup{data}}|p_{0,N})<+\infty$. Using Section D.2 the IPF sequence is
well-defined. Note that $\pi^{0}$ admits a density w.r.t. the Lebesgue measure
given by $p>0$. Let $n\in\mathbb{N}$ and assume that $p^{n}>0$ is given for
any $x_{0:N}\in\mathcal{X}$ by

$\textstyle{p^{n}(x_{0:N})=p_{\textup{data}}(x_{0})\prod_{k=0}^{N-1}q^{n-1}(x_{k+1}|x_{k}).}$
(285)

Using Section D.1 we get that for any $\pi\in\mathscr{P}_{N+1}$ such that
$\pi_{N}=p_{\textup{prior}}$ we have

$\textstyle{\operatorname{KL}(\pi|\pi^{2n})=\operatorname{KL}(p_{\textup{prior}}|\pi^{2n}_{0})+\int_{\mathbb{R}^{d}}\operatorname{KL}(\pi_{|N}|\pi^{2n}_{|N})p_{\textup{prior}}(x_{N})\mathrm{d}x_{N}.}$
(286)

Hence, we have that $\pi^{2n+1}=p_{\textup{prior}}\pi^{2n}_{|N}$. Since
$p^{n}>0$ we get that for any $\pi^{2n}_{|N}$ satisfies for any
$\mathsf{A}\in\mathcal{B}(\mathcal{X})$ and $x_{N}\in\mathbb{R}^{d}$

$\textstyle{\pi^{2n}_{|N}(\mathsf{A}|x_{N})=\int_{\mathsf{A}}p^{n}(x_{0:N})/p^{n}(x_{N})\mathrm{d}x_{0:N}\updelta_{x_{N}}(\mathsf{A}_{N})}.$
(287)

Therefore, $\pi^{2n+1}$ admits a density w.r.t. the Lebesgue measure denoted
$q^{n}$ and given for any $x_{0:N}\in\mathcal{X}$ by

$\displaystyle q^{n}(x_{0:N})$
$\displaystyle=p^{n}(x_{0:N})p_{\textup{prior}}(x_{N})/p^{n}(x_{N})$ (288)
$\displaystyle\textstyle{=p_{\textup{prior}}(x_{N})\prod_{k=0}^{N-1}p^{n}(x_{k+1}|x_{k})p^{n}(x_{k})/p^{n}(x_{k+1})=p_{\textup{prior}}(x_{N})\prod_{k=0}^{N-1}p^{n}(x_{k}|x_{k+1})},$
(289)

where we have used (285). Note that $q^{n}>0$. Similarly, we get that for any
$x_{0:N}\in\mathcal{X}$

$\textstyle{p^{n+1}(x_{0:N})=p_{\textup{data}}(x_{0})\prod_{k=0}^{N-1}q^{n}(x_{k+1}|x_{k}).}$
(290)

Note that again that $p^{n+1}>0$. We conclude by recursion.

###  D.4 Link with autoencoders

Consider the maximum likelihood problem

$\textstyle{q^{\star}=\operatorname*{arg\,max}\\{\mathbb{E}_{p_{\textup{data}}}[\log
q_{0}(X_{0})]\,:\;q\in\mathscr{P}_{d}(\mathcal{X}),\
q_{N}=p_{\textup{prior}}\\},}$ (291)

where $\mathscr{P}_{d}(\mathcal{X})$ is the subset of the probability
distribution over $\mathcal{X}$ which admit a density w.r.t. the Lebesgue
measure. Using Jensen’s inequality we have for any
$q\in\mathscr{P}_{d}(\mathcal{X})$

$\displaystyle\mathbb{E}_{p_{\textup{data}}}[\log q_{0}(X_{0})]$
$\displaystyle=\textstyle{\int_{\mathbb{R}^{d}}\log(\int_{(\mathbb{R}^{d})^{N-1}}q(x_{0:N})p(x_{1:N}|x_{0})/p(x_{1:N}|x_{0})\mathrm{d}x_{1:N})p_{0}(x_{0})\mathrm{d}x_{0}}$
(292)
$\displaystyle\geq\textstyle{\int_{\mathcal{X}}\log(q(x_{0:N})/p(x_{1:N}|x_{0}))p(x_{0:N})\mathrm{d}x_{0:N}}\geq-\operatorname{KL}(p|q)-\mathrm{H}(p_{0}).$
(293)

This Evidence Lower Bound (ELBO) is similar to the one identified in Ho et
al., (2020). Maximizing this ELBO is equivalent to solving the following
problem

$\textstyle{q^{0}=\operatorname*{arg\,min}\\{\operatorname{KL}(q|p)\,:\;q\in\mathscr{P}_{d}(\mathcal{X}),\
q_{N}=p_{\textup{prior}}\\},}$ (294)

which is the first step of IPF. Hence subsequent steps can be obtained by
maximizing ELBOs associated with the following maximum likelihood problems for
any $n\in\mathbb{N}$

$\displaystyle\textstyle{q^{\star}=\operatorname*{arg\,max}\\{\mathbb{E}_{p_{\textup{data}}}[\log
q_{0}(X_{0})]\,:\;q\in\mathscr{P}_{d}(\mathcal{X}),\
q_{N}=p_{\textup{prior}}\\},}$ (295)
$\displaystyle\textstyle{p^{\star}=\operatorname*{arg\,max}\\{\mathbb{E}_{p_{\textup{prior}}}[\log
p_{N}(X_{N})]\,:\;p\in\mathscr{P}_{d}(\mathcal{X}),\
p_{0}=p_{\textup{data}}\\}}.$ (296)

##  Appendix E Alternative variational formulations

In this section, we draw links between IPF and score-matching techniques. We
start by proving Section 3.3 in Section E.1. We then present alternative
variational formulations in Section E.2.

###  E.1 Proof of Section 3.3

We only prove (26) since the proof (27) is similar. Let $n\in\mathbb{N}$ and
$k\in\\{0,\dots,N-1\\}$. For any $x_{k+1}\in\mathbb{R}^{d}$ we have

$\textstyle{p^{n}_{k+1}(x_{k+1})=(4\uppi\gamma_{k+1})^{-d/2}\int_{\mathbb{R}^{d}}p^{n}(x_{k})\exp[-\|F_{k}^{n}(x_{k})-x_{k+1}\|^{2}/(4\gamma_{k+1})]\mathrm{d}x_{k},}$
(297)

with $F_{k}^{n}(x_{k})=x_{k}+\gamma_{k+1}f_{k}^{n}(x_{k})$. Since
$p^{n}_{k}>0$ is bounded using the dominated convergence theorem we have for
any $x_{k+1}\in\mathbb{R}^{d}$

$\textstyle{\nabla\log
p^{n}_{k+1}(x_{k+1})=\int_{\mathbb{R}^{d}}(F_{k}^{n}(x_{k})-x_{k+1})/(2\gamma_{k+1})p_{k|k+1}(x_{k}|x_{k+1})\mathrm{d}x_{k}.}$
(298)

Therefore we get that for any $x_{k+1}\in\mathbb{R}^{d}$

$\textstyle{b_{k+1}^{n}(x_{k+1})=\int_{\mathbb{R}^{d}}(F_{k}^{n}(x_{k})-F_{k}^{n}(x_{k+1}))/\gamma_{k+1}p_{k|k+1}(x_{k}|x_{k+1})\mathrm{d}x_{k}.}$
(299)

This is equivalent to

$\textstyle{B_{k+1}^{n}(x_{k+1})={\mathbb{E}}[X_{k+1}+F_{k}^{n}(X_{k})-F_{k}^{n}(X_{k+1})|X_{k+1}=x_{k+1}]},$
(300)

with $(X_{k},X_{k+1})\sim p_{k,k+1}(x_{k},x_{k+1})$. Hence, we get that

$\textstyle{B^{n}_{k+1}=\operatorname*{arg\,min}_{\mathrm{B}\in\mathrm{L}^{2}(\mathbb{R}^{d},\mathbb{R}^{d})}\mathbb{E}_{{p^{n}_{k,k+1}}}[\|\mathrm{B}(X_{k+1})-(X_{k+1}+F^{n}_{k}(X_{k})-F^{n}_{k}(X_{k+1}))\|^{2}]},$
(301)

which concludes the proof.

###  E.2 Variational formulas

In Section 3.3 and Section 3.3 we present a variational formula for
$B_{k+1}^{n}$ and $F_{k}^{n+1}$ for any $n\in\mathbb{N}$ and
$k\in\\{0,\dots,N-1\\}$, where we recall that for any $x\in\mathbb{R}^{d}$ we
have

$B_{k+1}^{n}(x)=x+\gamma_{k+1}b_{k+1}^{n}(x),\qquad
F_{k}^{n+1}=x+\gamma_{k+1}f_{k}^{n+1}(x),$ (302)

where we have

$b_{k+1}^{n}(x)=-f_{k}^{n}(x)+2\nabla\log p_{k+1}^{n}(x),\qquad
f_{k}^{n+1}(x)=-b_{k+1}^{n}(x)+2\nabla\log q_{k}^{n}(x).$ (303)

In the rest of this section we assume that for any $n\in\mathbb{N}$,
$k\in\\{0,\dots,N-1\\}$ and $x\in\mathbb{R}^{d}$ we have

$\displaystyle\textstyle{q_{k|k+1}^{n}(x_{k}|x_{k+1})=(4\uppi\gamma_{k+1})^{-d/2}\exp[-\|x_{k}-B_{k+1}^{n}(x_{k+1})\|^{2}/(4\gamma_{k+1})]},$
(304)
$\displaystyle\textstyle{p_{k+1|k}^{n+1}(x_{k+1}|x_{k})=(4\uppi\gamma_{k+1})^{-d/2}\exp[-\|x_{k+1}-F_{k}^{n+1}(x_{k})\|^{2}/(4\gamma_{k+1})]}.$
(305)

We recall that in this case Section 3.3 ensures that for any $n\in\mathbb{N}$
and $k\in\\{0,\dots,N-1\\}$

$\displaystyle\textstyle{B^{n}_{k+1}=\operatorname*{arg\,min}_{\mathrm{B}\in\mathrm{L}^{2}(\mathbb{R}^{d},\mathbb{R}^{d})}\mathbb{E}_{{p^{n}_{k,k+1}}}[\|\mathrm{B}(X_{k+1})-(X_{k+1}+F^{n}_{k}(X_{k})-F^{n}_{k}(X_{k+1}))\|^{2}]},$
(306)
$\displaystyle\textstyle{F^{n+1}_{k}=\operatorname*{arg\,min}_{\mathrm{F}\in\mathrm{L}^{2}(\mathbb{R}^{d},\mathbb{R}^{d})}\mathbb{E}_{q^{n}_{k,k+1}}[\|\mathrm{F}(X_{k})-(X_{k}+B^{n}_{k+1}(X_{k+1})-B^{n}_{k+1}(X_{k}))\|^{2}]}.$
(307)

In the rest of this section we derive other variational formulas and discuss
their practical limitations/advantages.

####  E.2.1 Score-matching formula and sum of networks

First, using (303) we have for any $n\in\mathbb{N}$, $k\in\\{0,\dots,N-1\\}$
and $x\in\mathbb{R}^{d}$

$\displaystyle b_{k+1}^{n}(x)=\textstyle{\alpha x+2\sum_{j=0}^{n}\nabla\log
p_{k+1}^{j}(x)-2\sum_{j=0}^{n-1}\nabla\log q_{k}^{j}(x),}$ (308)
$\displaystyle f_{k}^{n}(x)=\textstyle{-\alpha x+2\sum_{j=0}^{n-1}\nabla\log
q_{k}^{j}(x)-2\sum_{j=0}^{n-1}\nabla\log p_{k+1}^{j}(x).}$ (309)

In the following proposition we derive a variational formula for $\nabla\log
p_{k+1}^{n}$ and $\nabla\log q_{k}^{n}(x)$ for any $n\in\mathbb{N}$ and
$k\in\\{0,\dots,N-1\\}$.

######  Proposition .

For any $n\in\mathbb{N}$ and $k\in\\{0,\dots,N-1\\}$ we have

$\displaystyle\textstyle{\nabla\log
p_{k+1}^{n}=\operatorname*{arg\,min}_{u\in\mathrm{L}^{2}(\mathbb{R}^{d},\mathbb{R}^{d})}\mathbb{E}_{{p^{n}_{k,k+1}}}[\|u(X_{k+1})-(F_{k}^{n}(X_{k})-X_{k+1})/(2\gamma_{k+1})\|^{2}]},$
(310) $\displaystyle\textstyle{\nabla\log
q_{k}^{n}=\operatorname*{arg\,min}_{v\in\mathrm{L}^{2}(\mathbb{R}^{d},\mathbb{R}^{d})}\mathbb{E}_{q^{n}_{k,k+1}}[\|v(X_{k})-(B_{k+1}^{n}(X_{k+1})-X_{k})/(2\gamma_{k+1})\|^{2}]}.$
(311)

###### Proof.

The proof is similar to the one of Section 3.3 but is provided for
completeness. We only prove (317) since the proof (318) is similar. Let
$n\in\mathbb{N}$ and $k\in\\{0,\dots,N-1\\}$. For any
$x_{k+1}\in\mathbb{R}^{d}$ we have

$\textstyle{p^{n}_{k+1}(x_{k+1})=(4\uppi\gamma_{k+1})^{-d/2}\int_{\mathbb{R}^{d}}p^{n}(x_{k})\exp[-\|F_{k}^{n}(x_{k})-x_{k+1}\|^{2}/(4\gamma_{k+1})]\mathrm{d}x_{k},}$
(312)

with $F_{k}^{n}(x_{k})=x_{k}+\gamma_{k+1}f_{k}^{n}(x_{k})$. Since
$p^{n}_{k}>0$ is bounded using the dominated convergence theorem we have for
any $x_{k+1}\in\mathbb{R}^{d}$

$\textstyle{\nabla\log
p^{n}_{k+1}(x_{k+1})=\int_{\mathbb{R}^{d}}(F_{k}^{n}(x_{k})-x_{k+1})/(2\gamma_{k+1})p_{k|k+1}(x_{k}|x_{k+1})\mathrm{d}x_{k}.}$
(313)

This is equivalent to

$\textstyle{\nabla\log
p^{n}_{k+1}(x_{k+1})={\mathbb{E}}[(F_{k}^{n}(X_{k})-X_{k+1})/(2\gamma_{k+1})|X_{k+1}=x_{k+1}]},$
(314)

with $(X_{k},X_{k+1})\sim p_{k,k+1}(x_{k},x_{k+1})$. Hence, we get that

$\textstyle{\nabla\log
p^{n}_{k+1}=\operatorname*{arg\,min}_{u\in\mathrm{L}^{2}(\mathbb{R}^{d},\mathbb{R}^{d})}\mathbb{E}_{{p^{n}_{k,k+1}}}[\|u(X_{k+1})-(F^{n}_{k}(X_{k})-X_{k+1})/(2\gamma_{k+1})\|^{2}]},$
(315)

which concludes the proof. ∎

Note that (317) and (318) can be simplified upon remarking that for any
$n\in\mathbb{N}$ and $k\in\\{0,\dots,N-1\\}$

$\textstyle{X_{k+1}^{n}=F_{k}^{n}(X_{k}^{n})+\sqrt{2\gamma_{k+1}}Z_{k+1}^{n},\quad\tilde{X}_{k}^{n}=F_{k}^{n}(\tilde{X}_{k+1}^{n})+\sqrt{2\gamma_{k+1}}\tilde{Z}_{k+1}^{n},}$
(316)

with $\\{X_{k}^{n}\\}_{k=0}^{N}\sim p^{n}$,
$\\{\tilde{X}_{k}^{n}\\}_{k=0}^{N}\sim q^{n}$ and
$\\{(Z_{k+1}^{n},\tilde{Z}_{k+1}^{n})\,:\;n\in\mathbb{N},\
k\in\\{0,\dots,N-1\\}\\}$ a family of independent Gaussian random variables
with zero mean an identity covariance matrix. Using this result we get that
for any $n\in\mathbb{N}$ and $k\in\\{0,\dots,N-1\\}$

$\displaystyle\textstyle{\nabla\log
p_{k+1}^{n}=\operatorname*{arg\,min}_{u\in\mathrm{L}^{2}(\mathbb{R}^{d},\mathbb{R}^{d})}\mathbb{E}_{{p^{n}_{k,k+1}}}[\|u(X_{k+1})-Z_{k+1}^{n}/\sqrt{2\gamma_{k+1}}\|^{2}]},$
(317) $\displaystyle\textstyle{\nabla\log
q_{k}^{n}=\operatorname*{arg\,min}_{v\in\mathrm{L}^{2}(\mathbb{R}^{d},\mathbb{R}^{d})}\mathbb{E}_{q^{n}_{k,k+1}}[\|v(X_{k})-\tilde{Z}_{k+1}^{n}/\sqrt{2\gamma_{k+1}}\|^{2}]}.$
(318)

In practice, neural networks $u_{\alpha^{n}}(k,x)\approx\nabla\log
p_{k}^{n}(x)$, and $v_{\beta^{n}}(k,x)\approx\nabla\log q_{k}^{n}(x)$ are
used. Hence, we sample approximately from $q^{n}$ and $p^{n}$ for any
$n\in\mathbb{N}$ using the following recursion:

$\displaystyle\textstyle{\tilde{X}_{k}^{n}=\tilde{\tau}_{k+1}\tilde{X}_{k+1}^{n}+2\gamma_{k+1}\\{\sum_{j=0}^{n}u_{\alpha^{j}}(k+1,\tilde{X}_{k+1}^{n})-\sum_{j=0}^{n-1}v_{\beta^{j}}(k,\tilde{X}_{k+1}^{n})\\}+\sqrt{2\gamma_{k+1}}\tilde{Z}_{k+1}^{n},}$
(319)
$\displaystyle\textstyle{X_{k+1}^{n}=\tau_{k+1}X_{k}^{n}+2\gamma_{k+1}\\{\sum_{j=0}^{n}u_{\alpha^{j}}(k+1,X_{k}^{n})-\sum_{j=0}^{n}v_{\beta^{j}}(k,X_{k}^{n})\\}+\sqrt{2\gamma_{k+1}}Z_{k+1}^{n},}$
(320)

where $\tilde{\tau}_{k+1}=1+\alpha\gamma_{k+1}$,
$\tau_{k+1}=1-\alpha\gamma_{k+1}$ and $X_{0}^{n}\sim p_{\textup{data}}$,
$\tilde{X}_{N}^{n}\sim p_{\textup{prior}}$.

####  E.2.2 Drift-matching formula

In Section 3.3 we have given a variational formula for $B_{k+1}^{n}$ and
$F_{k}^{n+1}$ for any $n\in\mathbb{N}$ and $k\in\\{0,\dots,N-1\\}$. In Section
E.2.1 we have given a variational formula for $\nabla\log p_{k+1}^{n}$ and
$\nabla\log q_{k}^{n}$ for any $n\in\mathbb{N}$ and $k\in\\{0,\dots,N-1\\}$.
In the following proposition we give a variational formula for the drifts
$b_{k+1}^{n}$ and $f_{k}^{n+1}$.

######  Proposition .

For any $n\in\mathbb{N}$ and $k\in\\{0,\dots,N-1\\}$ we have

$\displaystyle\textstyle{b^{n}_{k+1}=\operatorname*{arg\,min}_{b\in\mathrm{L}^{2}(\mathbb{R}^{d},\mathbb{R}^{d})}\mathbb{E}_{{p^{n}_{k,k+1}}}[\|b(X_{k+1})-(F^{n}_{k}(X_{k})-F^{n}_{k}(X_{k+1}))/\gamma_{k+1}\|^{2}]}$
(321)
$\displaystyle\textstyle{f^{n+1}_{k}=\operatorname*{arg\,min}_{f\in\mathrm{L}^{2}(\mathbb{R}^{d},\mathbb{R}^{d})}\mathbb{E}_{q^{n}_{k,k+1}}[\|f(X_{k})-(B^{n}_{k+1}(X_{k+1})-B^{n}_{k+1}(X_{k}))/\gamma_{k+1}\|^{2}]}$
(322)

###### Proof.

The proof is similar to the one of Section 3.3 but is provided for
completeness. We only prove (321) since the proof (322) is similar. Let
$n\in\mathbb{N}$ and $k\in\\{0,\dots,N-1\\}$. For any
$x_{k+1}\in\mathbb{R}^{d}$ we have

$\textstyle{p^{n}_{k+1}(x_{k+1})=(4\uppi\gamma_{k+1})^{-d/2}\int_{\mathbb{R}^{d}}p^{n}(x_{k})\exp[-\|F_{k}^{n}(x_{k})-x_{k+1}\|^{2}/(4\gamma_{k+1})]\mathrm{d}x_{k},}$
(323)

with $F_{k}^{n}(x_{k})=x_{k}+\gamma_{k+1}f_{k}^{n}(x_{k})$. Since
$p^{n}_{k}>0$ is bounded using the dominated convergence theorem we have for
any $x_{k+1}\in\mathbb{R}^{d}$

$\textstyle{\nabla\log
p^{n}_{k+1}(x_{k+1})=\int_{\mathbb{R}^{d}}(F_{k}^{n}(x_{k})-x_{k+1})/(2\gamma_{k+1})p_{k|k+1}(x_{k}|x_{k+1})\mathrm{d}x_{k}.}$
(324)

Therefore we get that for any $x_{k+1}\in\mathbb{R}^{d}$

$\textstyle{b_{k+1}^{n}(x_{k+1})=\int_{\mathbb{R}^{d}}(F_{k}^{n}(x_{k})-F_{k}^{n}(x_{k+1}))/\gamma_{k+1}p_{k|k+1}(x_{k}|x_{k+1})\mathrm{d}x_{k}.}$
(325)

This is equivalent to

$\textstyle{b_{k+1}^{n}(x_{k+1})={\mathbb{E}}[(F_{k}^{n}(X_{k})-F_{k}^{n}(X_{k+1}))/\gamma_{k+1}|X_{k+1}=x_{k+1}]},$
(326)

with $(X_{k},X_{k+1})\sim p(x_{k},x_{k+1})$. Hence, we get that

$\textstyle{b^{n}_{k+1}=\operatorname*{arg\,min}_{b\in\mathrm{L}^{2}(\mathbb{R}^{d},\mathbb{R}^{d})}\mathbb{E}_{{p^{n}_{k,k+1}}}[\|b(X_{k+1})-(F^{n}_{k}(X_{k})-F^{n}_{k}(X_{k+1}))/\gamma_{k+1}\|^{2}]},$
(327)

which concludes the proof. ∎

In practice, neural networks $b_{\beta^{n}}(k,x)\approx b^{n}_{k}(x)$, and
$f_{\alpha^{n}}(k,x)\approx f^{n}_{k}(x)$ are used. Hence, we sample
approximately from $q^{n}$ and $p^{n}$ for any $n\in\mathbb{N}$ using the
following recursion:

$\displaystyle\textstyle{\tilde{X}_{k}^{n}=\tilde{X}_{k+1}^{n}+\gamma_{k+1}b_{\beta^{n}}(k+1,\tilde{X}_{k+1}^{n})+\sqrt{2\gamma_{k+1}}\tilde{Z}_{k+1}^{n},}$
(328)
$\displaystyle\textstyle{X_{k+1}^{n}=X_{k}^{n}+\gamma_{k+1}f_{\alpha^{n}}(k,X_{k}^{n})+\sqrt{2\gamma_{k+1}}Z_{k+1}^{n},}$
(329)

with $X_{0}^{n}\sim p_{\textup{data}}$, $\tilde{X}_{N}^{n}\sim
p_{\textup{prior}}$.

####  E.2.3 Discussion

We identify three variational formulas associated with Section 3.3, Section
E.2.1 and Section E.2.2. In practice we discard the approach of Section E.2.1
because it requires storing $2n$ neural networks to sample from $p^{n}$, see
(320). Hence the algorithm requires more memory as $n$ increases and the
sampling procedure requires $\mathcal{O}(nN)$ passes through a neural network.
The approaches described in Section 3.3 and Section E.2.2 yield sampling
procedures which only require $\mathcal{O}(N)$ passes through a neural network
and have fixed memory cost for any $n\in\mathbb{N}$. In practice we observed
that the approach of Section 3.3 yields better results. We conjecture that
this favorable behavior is mainly due to the architecture of the neural
networks used to approximate $B_{k+1}^{n}$ and $F_{k}^{n+1}$ which have
residual connections and therefore are better suited at representing functions
of the $x\mapsto x+\Phi(x)$ where $\Phi$ is a perturbation.

##  Appendix F Theoretical study of Schrödinger bridges and the IPF

In this section, we explore some of the theoretical properties of Schrödinger
bridges and the IPF procedure. Section 3.4 and Section 3.4 are proved in
Section F.1 and Section F.2 respectively.

###  F.1 Proof of Section 3.4

In this section, we prove Section 3.4. First we gather novel monotonicity
results for the IPF in Section F.1.1, see Section F.1.1. Then we prove our
quantitative convergence bounds in Theorem 4, see Section F.1.2.

####  F.1.1 Monotonicity results

We consider the static IPF recursion: $\pi^{0}=\mu\in\mathscr{P}_{2}$ and

$\displaystyle\pi^{2n+1}=\operatorname*{arg\,min}\left\\{\operatorname{KL}(\pi|\pi^{2n})\,:\;\pi\in\mathscr{P}_{2},\
\pi_{1}=\nu_{1}\right\\},$ (330)
$\displaystyle\pi^{2n+2}=\operatorname*{arg\,min}\left\\{\operatorname{KL}(\pi|\pi^{2n+1})\,:\;\pi\in\mathscr{P}_{2},\
\pi_{0}=\nu_{0}\right\\},$ (331)

where $\nu_{0},\nu_{1}\in\mathscr{P}(\mathbb{R}^{d})$. We also consider the
following assumption.

######  B 1.

$\mu$ is absolutely continuous w.r.t. $\mu_{0}\otimes\mu_{1}$ and
$\operatorname{KL}(\nu_{0}\otimes\nu_{1}|\mu)<+\infty$. In addition, $\nu_{i}$
and $\mu_{i}$ are equivalent for $i\in\\{0,1\\}$.

First we draw links between 1 and B 1.

######  Proposition .

1 implies B 1 with $\mu=p_{0,N}$.

###### Proof.

Since $p_{N}>0$ we get that $p_{N}$ and $p_{\textup{prior}}$ are equivalent.
Hence $\mu_{1}$ and $\nu_{1}$ are equivalent and $\mu_{0}=\nu_{0}$. Let us
show that $\mu$ is absolutely continuous w.r.t. $\mu_{0}\otimes\mu_{1}$, i.e.
that $p_{0,N}$ is absolutely continuous w.r.t. $p_{\textup{data}}\otimes
p_{N}$. Since $p_{N}>0$ we get that $p_{0,N}$ is absolutely continuous w.r.t.
$p_{\textup{data}}\otimes p_{N}$ with density $p_{N|0}/p_{N}$. Finally we have

$\displaystyle\textstyle{\int_{(\mathbb{R}^{d})^{2}}\log(p_{\textup{data}}(x_{0})p_{\textup{prior}}(x_{N})/(p_{\textup{data}}(x_{0})p_{N|0}(x_{N}|x_{0})))p_{\textup{data}}(x_{0})p_{\textup{prior}}(x_{N})\mathrm{d}x_{0}\mathrm{d}x_{N}}$
(332)
$\displaystyle\qquad=\textstyle{\int_{(\mathbb{R}^{d})^{2}}\log(p_{\textup{prior}}(x_{N})/p_{N|0}(x_{N}|x_{0}))p_{\textup{data}}(x_{0})p_{\textup{prior}}(x_{N})\mathrm{d}x_{0}\mathrm{d}x_{N}}$
(333)
$\displaystyle\qquad\textstyle{\leq|\mathrm{H}(p_{\textup{prior}})|+\int_{\mathbb{R}^{d}}|\log
p_{N|0}(x_{N}|x_{0})|p_{\textup{data}}(x_{0})p_{\textup{prior}}(x_{N})\mathrm{d}x_{0}\mathrm{d}x_{N}<+\infty}$
(334)

which concludes the proof. ∎

In this section we prove the following proposition.

######  Proposition .

Assume B 1. Then, the IPF sequence is well-defined and for any
$n\in\mathbb{N}$ with $n\geq 1$ we have

$\operatorname{KL}(\pi^{n+1}|\pi^{n})\leq\operatorname{KL}(\pi^{n-1}|\pi^{n}),\qquad\operatorname{KL}(\pi^{n}|\pi^{n+1})\leq\operatorname{KL}(\pi^{n}|\pi^{n-1}).$
(335)

In addition, the following results hold:

  1. (a)

$(\|\pi^{n+1}-\pi^{n}\|_{\mathrm{TV}})_{n\in\mathbb{N}}$ and
$(\operatorname{J}(\pi^{n+1},\pi^{n}))_{n\in\mathbb{N}}$ are non-increasing.

  2. (b)

$(\operatorname{KL}(\pi^{2n+1}|\pi^{2n}))_{n\in\mathbb{N}}$ and
$(\operatorname{KL}(\pi^{2n+2}|\pi^{2n+1}))_{n\in\mathbb{N}}$ are non-
increasing.

  3. (c)

$(\operatorname{KL}(\pi^{2n+1}_{1}|\nu_{1}))_{n\in\mathbb{N}}$ and
$(\operatorname{KL}(\pi^{2n}_{0}|\nu_{0}))_{n\in\mathbb{N}}$ are non-
increasing.

  4. (d)

$(\|\pi^{2n+1}_{1}-\nu_{1}\|_{\mathrm{TV}})_{n\in\mathbb{N}}$ and
$(\|\pi^{2n}_{0}-\nu_{0}\|_{\mathrm{TV}})_{n\in\mathbb{N}}$ are non-
increasing.

First, we show that under B 1, the IPF sequence is well-defined and is
associated with a sequence of potentials.

######  Proposition .

Assume B 1. Then, the IPF sequence is well-defined and there exist
$(a_{n})_{n\in\mathbb{N}}$ and $(b_{n})_{n\in\mathbb{N}}$ such that for any
$n\in\mathbb{N}$, $a_{n},b_{n}:\ \mathbb{R}^{d}\to\left(0,+\infty\right)$ and
for any $x,y\in\mathbb{R}^{d}$

$\displaystyle\textstyle{(\mathrm{d}\pi^{2n+1}/\mathrm{d}(\mu_{0}\otimes\mu_{1}))(x,y)=a_{n}(x)h(x,y)b_{n}(y)}$
(336)
$\displaystyle\textstyle{(\mathrm{d}\pi^{2n+2}/\mathrm{d}(\mu_{0}\otimes\mu_{1}))(x,y)=a_{n+1}(x)h(x,y)b_{n}(y),}$
(337)

and

$\displaystyle\textstyle{v_{0}(x)=a_{n+1}(x)\int_{\mathbb{R}^{d}}h(x,y)b_{n}(y)\mathrm{d}\mu_{1}(y),\quad
v_{1}(y)=b_{n}(y)\int_{\mathbb{R}^{d}}h(x,y)a_{n}(x)\mathrm{d}\mu_{0}(x),}$
(338)

where $v_{i}=\mathrm{d}\nu_{i}/\mathrm{d}\mu_{i}$ for $i\in\\{0,1\\}$.

###### Proof.

First, we show that the IPF sequence is well-defined. Note that $\pi^{1}$ is
well-defined since $\operatorname{KL}(\nu_{0}\otimes\nu_{1}|\mu)<+\infty$.
Assume that $\\{\pi^{\ell}\\}_{\ell=1}^{n}$ is well-defined. Using (Csiszár,,
1975, Theorem 2.2) we have

$\textstyle{\operatorname{KL}(\nu_{0}\otimes\nu_{1}|\mu)=\operatorname{KL}(\nu_{0}\otimes\nu_{1}|\pi^{n})+\sum_{\ell=0}^{n-1}\operatorname{KL}(\pi^{\ell+1}|\pi^{\ell}).}$
(339)

In particular, $\operatorname{KL}(\nu_{0}\otimes\nu_{1}|\pi^{n})<+\infty$ and
$\pi^{n+1}$ is well-defined. We conclude by recursion.

Using (Csiszár,, 1975, Theorem 3.1) and B 1, there exists
$(\tilde{b}_{n})_{n\in\mathbb{N}}$ such that for any $n\in\mathbb{N}$,
$\tilde{b}_{n}:\ \mathbb{R}^{d}\to\left[0,+\infty\right)$ and for any
$x,y\in\mathsf{A}_{n}$,
$(\mathrm{d}\pi^{2n+1}/\mathrm{d}\pi^{2n})(x,y)=\tilde{b}_{n}(y)$ with
$\mathsf{A}_{n}\in\mathcal{B}(\mathbb{R}^{d})$,
$\tilde{\pi}(\mathsf{A}_{n})=0$ for any $\tilde{\pi}$ such that
$\tilde{\pi}_{1}=\nu_{1}$ and
$\operatorname{KL}(\tilde{\pi}|\pi^{2n})<+\infty$. In particular we have
$(\nu_{0}\otimes\nu_{1})(\mathsf{A}_{n})=0$. Since $\nu_{i}$ is equivalent to
$\mu_{i}$ for any $i\in\\{0,1\\}$ we have
$(\mu_{0}\otimes\mu_{1})(\mathsf{A}_{n})=0$. Similarly, there exists
$(\tilde{a}_{n})_{n\in\mathbb{N}}$ such that for any $n\in\mathbb{N}$,
$\tilde{a}_{n}:\ \mathbb{R}^{d}\to\left[0,+\infty\right)$ and for any
$x,y\in\mathsf{B}_{n}$,
$(\mathrm{d}\pi^{2n+2}/\mathrm{d}\pi^{2n+1})(x,y)=\tilde{a}_{n+1}(x)$ with
$\mathsf{B}_{n}\in\mathcal{B}(\mathbb{R}^{d})$ and
$(\mu_{0}\otimes\mu_{1})(\mathsf{B}_{n})=0$. As a result, there exist
$(a_{n})_{n\in\mathbb{N}}$ and $(b_{n})_{n\in\mathbb{N}}$ with $a_{n}:\
\mathbb{R}^{d}\to\left[0,+\infty\right)$ and $b_{n}:\
\mathbb{R}^{d}\to\left[0,+\infty\right)$ such that for any $n\in\mathbb{N}$
and $x,y\in\mathbb{R}^{d}$

$\displaystyle\textstyle{(\mathrm{d}\pi^{2n+1}/\mathrm{d}(\mu_{0}\otimes\mu_{1}))(x,y)=a_{n}(x)h(x,y)b_{n}(y)}$
(340)
$\displaystyle\textstyle{(\mathrm{d}\pi^{2n+2}/\mathrm{d}(\mu_{0}\otimes\mu_{1}))(x,y)=a_{n+1}(x)h(x,y)b_{n}(y),}$
(341)

where $h=\mathrm{d}\mu/\mathrm{d}(\mu_{0}\otimes\mu_{1})$ and $a_{0}=1$. In
addition, setting $b_{-1}=1$, we have for any $x,y\in\mathbb{R}^{d}$,

$(\mathrm{d}\pi^{0}/\mathrm{d}(\mu_{0}\otimes\mu_{1}))(x,y)=a_{0}(x)h(x,y)b_{-1}(y).$
(342)

Using that $\nu_{i}$ is absolutely continuous w.r.t. $\mu_{i}$ for
$i\in\\{0,1\\}$ with density $v_{i}:\ \mathbb{R}^{d}\to\left(0,+\infty\right)$
we get that for any $x,y\in\mathbb{R}^{d}$ and $n\in\mathbb{N}$

$\displaystyle\textstyle{v_{0}(x)=a_{n+1}(x)\int_{\mathbb{R}^{d}}h(x,y)b_{n}(y)\mathrm{d}\mu_{1}(y),\quad
v_{1}(y)=b_{n}(y)\int_{\mathbb{R}^{d}}h(x,y)a_{n}(x)\mathrm{d}\mu_{0}(x).}$
(343)

Since $v_{0},v_{1}>0$ for any $n\in\mathbb{N}$, $a_{n},b_{n}>0$. ∎

Note that the system of equations (338) corresponds to iteratively solving the
Schrödinger system, see Léonard, 2014b  for a survey. In addition, (338) has
connections with Fortet’s mapping (Léonard,, 2019; Fortet,, 1940).

In the rest of the section we detail the proof of Section 3.4. We start by
deriving identities between the marginals of the IPF and its joint
distribution both w.r.t. the Kullback-Leibler divergence and the total
variation norm in Section F.1.1. Second, we establish that
$(\|\pi^{n+1}-\pi^{n}\|_{\mathrm{TV}})_{n\in\mathbb{N}}$ is non-increasing in
Section F.1.1. Then, we prove (335) in Section F.1.1. We conclude with the
proof of Section F.1.1.

######  Lemma .

Assume B 1. Then, for any $n\in\mathbb{N}$ we have

$\|\pi^{2n+1}-\pi^{2n}\|_{\mathrm{TV}}=\|\pi^{2n}_{1}-\nu_{1}\|_{\mathrm{TV}},\qquad\|\pi^{2n+2}-\pi^{2n+1}\|_{\mathrm{TV}}=\|\pi^{2n+1}_{0}-\nu_{0}\|_{\mathrm{TV}}.$
(344)

In addition, we have

$\operatorname{KL}(\pi^{2n}|\pi^{2n+1})=\operatorname{KL}(\pi^{2n}_{1}|\nu_{1}),\qquad\operatorname{KL}(\pi^{2n+1}|\pi^{2n+2})=\operatorname{KL}(\pi^{2n+1}_{0}|\nu_{0}).$
(345)

###### Proof.

We divide the proof into two parts. First, we prove (344). Second, we show
that (345) holds.

  1. (a)

We only show that for any $n\in\mathbb{N}$ we have
$\|\pi^{2n+1}-\pi^{2n}\|_{\mathrm{TV}}=\|\pi^{2n}_{1}-\nu_{1}\|_{\mathrm{TV}}$.
The proof that for any $n\in\mathbb{N}$,
$\|\pi^{2n+2}-\pi^{2n+1}\|_{\mathrm{TV}}=\|\pi^{2n+1}_{0}-\nu_{0}\|_{\mathrm{TV}}$
is similar. Let $n\in\mathbb{N}$. Using (336) and (338) we have

$\displaystyle\|\pi^{2n+1}-\pi^{2n}\|_{\mathrm{TV}}$
$\displaystyle=\textstyle{\int_{(\mathbb{R}^{d})^{2}}\left|b_{n}(y)-b_{n-1}(y)\right|a_{n}(x)h(x,y)\mathrm{d}\mu_{0}(x)\mathrm{d}\mu_{1}(y)}$
(346)
$\displaystyle=\textstyle{\int_{\mathbb{R}^{d}}\left|1-b_{n-1}(x)/b_{n}(x)\right|\mathrm{d}\nu_{1}(y).}$
(347)

In addition, we have that for any $\mathsf{A}\in\mathcal{B}(\mathbb{R}^{d})$

$\textstyle{\pi^{2n}_{1}(\mathsf{A})=\int_{\mathbb{R}^{d}\times\mathsf{A}}a_{n}(x)b_{n-1}(y)h(x,y)\mathrm{d}\mu_{0}(x)\mathrm{d}\mu_{1}(y)=\int_{\mathsf{A}}(b_{n-1}/b_{n})(y)\mathrm{d}\nu_{1}(y).}$
(348)

We get that for any $y\in\mathbb{R}^{d}$,
$(\mathrm{d}\pi_{1}^{2n}/\mathrm{d}\nu_{1})(y)=(b_{n-1}/b_{n})(y)$. Hence,
using (346) we get that

$\textstyle{\|\pi^{2n}_{1}-\nu_{1}\|_{\mathrm{TV}}=\int_{\mathbb{R}^{d}}\left|1-a_{n}(x)/a_{n+1}(x)\right|\mathrm{d}\nu_{0}(x)=\|\pi^{2n+1}-\pi^{2n}\|_{\mathrm{TV}}.}$
(349)

  2. (b)

We only show that for any $n\in\mathbb{N}$ we have
$\operatorname{KL}(\pi^{2n}|\pi^{2n+1})=\operatorname{KL}(\pi^{2n}_{1}|\nu_{1})$.
The proof that for any $n\in\mathbb{N}$,
$\operatorname{KL}(\pi^{2n+1}|\pi^{2n+2})=\operatorname{KL}(\pi^{2n+1}_{0}|\nu_{0})$
is similar. Let $n\in\mathbb{N}$. Using that for any $x,y\in\mathbb{R}^{d}$,
$(\mathrm{d}\pi^{2n}_{1}/\mathrm{d}\nu_{1})(y)=b_{n-1}(y)/b_{n}(y)$ and that
$(\mathrm{d}\pi^{2n+1}/\mathrm{d}\pi^{2n})(x,y)=b_{n}(y)/b_{n-1}(y)$ we have

$\operatorname{KL}(\pi^{2n}|\pi^{2n+1})=-\textstyle{\int_{\mathbb{R}^{d}}\log(b_{n}(y)/b_{n-1}(y))\mathrm{d}\pi^{2n}_{1}(y)}=\operatorname{KL}(\pi^{2n}_{1}|\nu_{1}).$
(350)

This concludes the proof.

∎

######  Lemma .

Assume B 1. Then $(\|\pi^{n+1}-\pi^{n}\|_{\mathrm{TV}})_{n\in\mathbb{N}}$ is
non-increasing.

###### Proof.

We only prove that for any $n\in\mathbb{N}$ with $n\geq 1$,
$\|\pi^{2n+1}-\pi^{2n}\|_{\mathrm{TV}}\leq\|\pi^{2n}-\pi^{2n-1}\|_{\mathrm{TV}}$.
The proof that for any $n\in\mathbb{N}$,
$\|\pi^{2n+2}-\pi^{2n+1}\|_{\mathrm{TV}}\leq\|\pi^{2n+1}-\pi^{2n}\|_{\mathrm{TV}}$
is similar. Let $n\in\mathbb{N}$ with $n\geq 1$. Similarly to the proof of
Section F.1.1 we have that

$\textstyle{\|\pi^{2n+1}-\pi^{2n}\|_{\mathrm{TV}}=\int_{\mathbb{R}^{d}}\left|1-b_{n-1}(y)/b_{n}(y)\right|\mathrm{d}\nu_{1}(y)=\int_{\mathbb{R}^{d}}\left|b_{n}^{-1}(y)-b_{n-1}^{-1}(y)\right|b_{n-1}(y)\mathrm{d}\nu_{1}(y).}$
(351)

In addition, we have that for any $y\in\mathbb{R}^{d}$

$\textstyle{\left|b_{n-1}^{-1}(y)-b_{n}^{-1}(y)\right|\leq
v_{1}^{-1}(y)\int_{\mathbb{R}^{d}}h(x,y)\left|a_{n-1}(x)-a_{n}(x)\right|\mathrm{d}\mu_{0}(x).}$
(352)

Combining this result and (351) we get that

$\displaystyle\|\pi^{2n+1}-\pi^{2n}\|_{\mathrm{TV}}$
$\displaystyle\leq\textstyle{\int_{\mathbb{R}^{d}}\left|b_{n-1}^{-1}(y)-b_{n}^{-1}(y)\right|b_{n-1}(y)\mathrm{d}\nu_{1}(y)}$
(353)
$\displaystyle\leq\textstyle{\int_{(\mathbb{R}^{d})^{2}}\left|a_{n}(x)-a_{n-1}(x)\right|h(x,y)b_{n-1}(y)\mathrm{d}\mu_{0}(x)\mathrm{d}\mu_{1}(y)}$
(354)
$\displaystyle\leq\textstyle{\int_{\mathbb{R}^{d}}\left|1-a_{n-1}(x)/a_{n}(x)\right|\mathrm{d}\nu_{0}(x)\leq\|\pi^{2n}-\pi^{2n-1}\|_{\mathrm{TV}}},$
(355)

which concludes the proof. ∎

######  Lemma .

Assume B 1. Then for any $n\in\mathbb{N}$ with $n\geq 1$ we have

$\operatorname{KL}(\pi^{n+1}|\pi^{n})\leq\operatorname{KL}(\pi^{n-1}|\pi^{n}),\qquad\operatorname{KL}(\pi^{n}|\pi^{n+1})\leq\operatorname{KL}(\pi^{n}|\pi^{n-1}).$
(356)

###### Proof.

Using Section F.1.1 and the data processing theorem (Ambrosio et al.,, 2008,
Lemma 9.4.5) we get that for any $n\in\mathbb{N}$

$\operatorname{KL}(\pi^{2n}|\pi^{2n+1})=\operatorname{KL}(\pi^{2n}_{1}|\nu_{1})\leq\operatorname{KL}(\pi^{2n}|\pi^{2n+1}).$
(357)

Similarly, we get that for any $n\in\mathbb{N}$,
$\operatorname{KL}(\pi^{2n+1}|\pi^{2n+2})\leq\operatorname{KL}(\pi^{2n+1}|\pi^{2n})$.
Hence, we get that for any $n\in\mathbb{N}$,
$\operatorname{KL}(\pi^{n}|\pi^{n+1})\leq\operatorname{KL}(\pi^{n}|\pi^{n-1})$.

In addition, using that for any $n\in\mathbb{N}$ with $n\geq 1$ and
$x,y\in\mathbb{R}^{d}$, we have that $\pi^{2n+1}_{1}=\nu_{1}$ and
$(\mathrm{d}\pi^{2n+1}/\mathrm{d}\pi^{2n})(x,y)=b_{n}(y)/b_{n-1}(y)$ we get
for any $n\in\mathbb{N}$ with $n\geq 1$

$\displaystyle\textstyle{\operatorname{KL}(\pi^{2n+1}|\pi^{2n})=-\int_{\mathbb{R}^{d}}\log(b_{n-1}(y)/b_{n}(y))\mathrm{d}\nu_{1}(y).}$
(358)

Using Jensen’s inequality we have for any $n\in\mathbb{N}$

$\displaystyle\textstyle{-\log(b_{n-1}(y)/b_{n}(y))\leq-\log\left(\left.\int_{\mathbb{R}^{d}}h(x,y)a_{n}(x)\mathrm{d}\mu_{0}(x)\middle/\int_{\mathbb{R}^{d}}h(x,y)a_{n-1}(x)\mathrm{d}\mu_{0}(x)\right.\right)}$
(359)
$\displaystyle\qquad\leq\textstyle{-\log\left(\left.\int_{\mathbb{R}^{d}}(a_{n}(x)/a_{n-1}(x))h(x,y)a_{n-1}(x)\mathrm{d}\mu_{0}(y)\middle/\int_{\mathbb{R}^{d}}h(x,y)a_{n-1}(x)\mathrm{d}\mu_{0}(x)\right.\right)}$
(360)
$\displaystyle\qquad\leq\textstyle{-\int_{\mathbb{R}^{d}}\log(a_{n}(x)/a_{n-1}(x))b_{n-1}(y)h(x,y)a_{n-1}(x)/v_{1}(y)\mathrm{d}\mu_{0}(x).}$
(361)

Combining this result, (358), Fubini’s theorem and that for any
$n\in\mathbb{N}$ with $n\geq 1$ and $x\in\mathbb{R}^{d}$,
$(\mathrm{d}\pi^{2n-1}_{0}/\mathrm{d}\nu_{0})(x)=a_{n-1}(x)/a_{n}(x)$ we get
that for any $n\in\mathbb{N}$ with $n\geq 1$

$\displaystyle\operatorname{KL}(\pi^{2n+1}|\pi^{2n})$
$\displaystyle\textstyle{\leq\int_{(\mathbb{R}^{d})^{2}}\log(a_{n-1}(x)/a_{n}(x))a_{n-1}(x)h(x,y)b_{n-1}(y)\mathrm{d}\mu_{1}(y)\mathrm{d}\mu_{0}(x)}$
(362)
$\displaystyle\textstyle{\leq\int_{(\mathbb{R}^{d})^{2}}\log(a_{n-1}(x)/a_{n}(x))(a_{n-1}(x)/a_{n}(x))\mathrm{d}\nu_{0}(x)\leq\operatorname{KL}(\pi^{2n-1}_{0}|\nu_{0}).}$
(363)

Using Section F.1.1 (or the data processing theorem) we get that for any
$n\in\mathbb{N}$ with $n\geq 1$,
$\operatorname{KL}(\pi^{2n+1}|\pi^{2n})\leq\operatorname{KL}(\pi^{2n-1}|\pi^{2n})$.
Similarly, we get that for any $n\in\mathbb{N}$,
$\operatorname{KL}(\pi^{2n+2}|\pi^{2n+1})\leq\operatorname{KL}(\pi^{2n}|\pi^{2n+1})$,
which concludes the proof. ∎

We now turn to the proof of Section F.1.1

###### Proof.

First, (335) is a direct consequence of Section F.1.1. Using Section F.1.1 we
get that $(\|\pi^{n+1}-\pi^{n}\|_{\mathrm{TV}})_{n\in\mathbb{N}}$ is non-
increasing. Since for any $\eta_{0},\eta_{1}\in\mathscr{P}(\mathbb{R}^{d})$ we
have
$\operatorname{J}(\eta_{0},\eta_{1})=(1/2)\\{\operatorname{KL}(\eta_{0}|\eta_{1})+\operatorname{KL}(\eta_{0}|\eta_{1})\\}$
and using (335), we get that
$(\operatorname{J}(\pi_{n+1},\pi_{n}))_{n\in\mathbb{N}}$ is non-increasing
which proves Section F.1.1-(a). Section F.1.1-(b) is a straightforward
consequence of (335). Section F.1.1-(c) is a consequence of Section F.1.1 and
Section F.1.1-(a). Finally, Section F.1.1-(c) is a consequence of Section
F.1.1 and (335). ∎

Note that we also have that for any $n\in\mathbb{N}$,
$(\operatorname{KL}(\pi^{2n}|\pi^{2n+1}))_{n\in\mathbb{N}}$ and
$(\operatorname{KL}(\pi^{2n+1}|\pi^{2n+2}))_{n\in\mathbb{N}}$ are non-
increasing.

####  F.1.2 Quantitative convergence bounds

In this section we prove the following theorem.

######  Theorem 4.

Assume B 1. Then, the IPF sequence $(\pi^{n})_{n\in\mathbb{N}}$ is well-
defined. Then, the following hold:

  1. (a)

$\lim_{n\to+\infty}n^{1/2}\left\\{\|\pi_{0}^{n}-\nu_{0}\|_{\mathrm{TV}}+\|\pi_{1}^{n}-\nu_{1}\|_{\mathrm{TV}}\right\\}=0.$

  2. (b)

$\lim_{n\to+\infty}n\left\\{\operatorname{KL}(\pi_{0}^{n}|\nu_{0})+\operatorname{KL}(\pi_{1}^{n}|\nu_{1})\right\\}=0.$

We begin with Section F.1.2 which is an adaption of (Ruschendorf et al.,,
1995, Proposition 2.1). Then we state and prove Section F.1.2 which is a
classical lemma from real analysis. Combining these two lemmas and the
monotonicity results from Section F.1.1 conclude the proof.

######  Lemma .

Assume B 1. Then, $(\pi^{n})_{n\in\mathbb{N}}$ is well-defined and we have
$\sum_{n\in\mathbb{N}}\operatorname{KL}(\pi^{n+1}|\pi^{n})<+\infty$.

###### Proof.

The sequence is well-defined using Section F.1.1. In addition, using
(Csiszár,, 1975, Theorem 2.2) we have for any $n\in\mathbb{N}$

$\textstyle{\operatorname{KL}(\pi^{\star}|\pi^{0})=\operatorname{KL}(\pi^{\star}|\pi^{n})+\sum_{k=0}^{n-1}\operatorname{KL}(\pi^{k+1}|\pi^{k}),}$
(364)

which concludes the proof. ∎

######  Lemma .

Let $(c_{n})_{n\in\mathbb{N}}\in\left[0,+\infty\right)^{\mathbb{N}}$ a non-
increasing sequence such that $\sum_{n\in\mathbb{N}}c_{n}<+\infty$. Then
$\lim_{n\to+\infty}c_{n}n=0$.

###### Proof.

Let $\varepsilon>0$ and $n_{0}\in\mathbb{N}$ such that for any $n\geq n_{0}$,
$\sum_{k=n}^{+\infty}c_{k}\leq\varepsilon$. Let $n\in\mathbb{N}$ with $n\geq
2n_{0}$. Note that $n-n_{0}\geq n/2\geq n_{0}$. Therefore we have
$\varepsilon\geq(n-n_{0})c_{n}\geq(n/2)c_{n}$. Hence, for any $n\in\mathbb{N}$
with $n\geq 2n_{0}$, $c_{n}n\leq 2\varepsilon$, which concludes the proof. ∎

We now conclude with the proof of Theorem 4.

###### Proof.

Since $(\operatorname{KL}(\pi^{2n+1}|\pi^{2n}))_{n\in\mathbb{N}}$ and
$(\operatorname{KL}(\pi^{2n+2}|\pi^{2n+1}))_{n\in\mathbb{N}}$ are non-
increasing by Section F.1.1, using Section F.1.2, we get that

$\lim_{n\to+\infty}n\left\\{\operatorname{KL}(\pi_{0}^{n}|\nu_{0})+\operatorname{KL}(\pi_{1}^{n}|\nu_{1})\right\\}=0.$
(365)

We conclude upon using Pinsker’s inequality (Bakry et al.,, 2014, Equation
5.2.2). ∎

###  F.2 Proof of Section 3.4

Similarly to Section F.1, we consider the static IPF recursion:
$\pi^{0}=\mu\in\mathscr{P}_{2}$ and

$\displaystyle\pi^{2n+1}=\operatorname*{arg\,min}\left\\{\operatorname{KL}(\pi|\pi^{2n})\,:\;\pi\in\mathscr{P}_{2},\
\pi_{1}=\nu_{1}\right\\},$ (366)
$\displaystyle\pi^{2n+2}=\operatorname*{arg\,min}\left\\{\operatorname{KL}(\pi|\pi^{2n+1})\,:\;\pi\in\mathscr{P}_{2},\
\pi_{0}=\nu_{0}\right\\},$ (367)

where $\nu_{0},\nu_{1}\in\mathscr{P}(\mathbb{R}^{d})$. We recall that in this
context if the Schrödinger bridge $\pi^{\star}$ exists it is given by

$\pi^{\star}=\operatorname*{arg\,min}\\{\operatorname{KL}(\pi|\mu)\,:\;\pi\in\mathscr{P}_{2},\
\pi_{0}=\nu_{0},\ \pi_{1}=\nu_{1}\\}.$ (368)

In this section, we prove the following proposition which directly implies
Section 3.4.

######  Proposition .

Assume B 1 and denote $h=\mathrm{d}\mu/(\mathrm{d}\mu_{0}\otimes\mu_{1})$.
Assume that
$h\in\mathrm{C}(\mathbb{R}^{d}\times\mathbb{R}^{d},\left(0,+\infty\right])$
and that there exist
$\Phi_{0},\Phi_{1}\in\mathrm{C}(\mathbb{R}^{d},\left(0,+\infty\right))$ such
that for any $x,y\in\mathbb{R}^{d}$

$\displaystyle h(x,y)\leq\Phi_{0}(x)\Phi_{1}(y),\text{~{}and}$ (369)
$\displaystyle\textstyle{\int_{\mathbb{R}^{d}\times\mathbb{R}^{d}}(\left|\log
h(x_{0},x_{1})\right|+\left|\log\Phi_{0}(x_{0})\right|+\left|\log\Phi_{1}(x_{1})\right|)\mathrm{d}\mu_{0}(x_{0})\mathrm{d}\mu_{1}(x_{1})<+\infty.}$
(370)

Then there exists a solution $\pi^{\star}$ to the Schrödinger bridge. Assume
that the IPF sequence satisfies
$\lim_{n\to+\infty}\|\pi^{n}-\pi^{\infty}\|_{\mathrm{TV}}=0$ with
$\pi^{\infty}\in\mathscr{P}_{2}$. If $\mu$ is absolutely continuous w.r.t.
$\pi^{\infty}$ then $\pi^{\infty}=\pi^{\star}$.

We begin with an adaptation of (Rüschendorf and Thomsen,, 1993, Proposition
2).

######  Proposition .

Let $\mu\in\mathscr{P}_{2}$ and assume that $\mu$ is absolutely continuous
w.r.t. $\mu_{0}\otimes\mu_{1}$. Let $(a_{n})_{n\in\mathbb{N}}$ and
$(b_{n})_{n\in\mathbb{N}}$ such that for any $n\in\mathbb{N}$, $a_{n}:\
\mathbb{R}^{d}\to\left(0,+\infty\right)$ and $b_{n}:\
\mathbb{R}^{d}\to\left(0,+\infty\right)$. Assume that there exists $\Phi:\
(\mathbb{R}^{d})^{2}\to\left[0,+\infty\right)$ and
$\mathsf{A}\in\mathcal{B}(\mathbb{R}^{d})\otimes\mathcal{B}(\mathbb{R}^{d})$
with $\mu(\mathsf{A})=1$ such that for any $(x,y)\in\mathsf{A}$

$\lim_{n\to+\infty}a_{n}(x)b_{n}(y)=\Phi(x,y).$ (371)

Then, there exist $a:\ \mathbb{R}^{d}\to\left[0,+\infty\right)$, $b:\
\mathbb{R}^{d}\to\left[0,+\infty\right)$ and
$\mathsf{B}\in\mathcal{B}(\mathbb{R}^{d})\otimes\mathcal{B}(\mathbb{R}^{d})$
with $\mu(\mathsf{B})=1$ such that for any $x,y\in\mathsf{B}$

$\Phi(x,y)=a(x)b(y),\qquad\text{or }\quad\Phi(x,y)=0.$ (372)

###### Proof.

Let $\tilde{\mathsf{A}}=\\{(x,y)\in(\mathbb{R}^{d})^{2}\,:\;\Phi(x,y)=0\\}$
and $\mathsf{A}_{a}=\tilde{\mathsf{A}}\cap\mathsf{A}$ and
$\mathsf{A}_{b}=\tilde{\mathsf{A}}^{\mathrm{c}}\cap\mathsf{A}$. If
$\mathsf{A}_{b}=\emptyset$, we conclude the proof. Otherwise, let
$(x_{0},y_{0})\in\mathsf{A}_{b}$. Let
$\mathsf{C}_{0},\mathsf{C}_{1}\in\mathcal{B}(\mathbb{R}^{d})\otimes\mathcal{B}(\mathbb{R}^{d})$
be given by

$\displaystyle\mathsf{C}_{0}^{0}$
$\displaystyle=\\{x\in\mathbb{R}^{d}\,:\;\lim_{n\to+\infty}a_{n}^{0}(x)=a^{0}(x)\
\text{exists and $a^{0}(x)>0$}\\},$ (373) $\displaystyle\mathsf{C}_{1}^{0}$
$\displaystyle=\\{y\in\mathbb{R}^{d}\,:\;\lim_{n\to+\infty}b_{n}^{0}(y)=b^{0}(y)\
\text{exists and $b^{0}(y)>0$}\\},$ (374)

where for any $n\in\mathbb{N}$ and $x,y\in\mathbb{R}^{d}$,
$a_{n}^{0}(x)=a_{n}(x)/a_{n}(x_{0})$ and $b_{n}^{0}(y)=b_{n}(y)a_{n}(x_{0})$,
which is well-defined since for any $n\in\mathbb{N}$, $a_{n}(x_{0})>0$. Note
that $x_{0}\in\mathsf{C}_{0}^{0}$ and that $y_{0}\in\mathsf{C}_{1}^{0}$. If
$\mathsf{A}_{b}\subset\mathsf{C}_{0}^{0}\times\mathsf{C}_{1}^{0}$, we conclude
the proof. Otherwise, let
$(x_{1},y_{1})\in\mathsf{A}_{b}\cap(\mathsf{C}_{0}^{0}\times\mathsf{C}_{1}^{0})^{\mathrm{c}}$
and define

$\displaystyle\mathsf{C}_{0}^{1}$
$\displaystyle=\\{x\in\mathbb{R}^{d}\,:\;\lim_{n\to+\infty}a_{n}^{1}(x)=a^{1}(x)\
\text{exists and $a^{1}(x)>0$}\\},$ (375) $\displaystyle\mathsf{C}_{1}^{1}$
$\displaystyle=\\{y\in\mathbb{R}^{d}\,:\;\lim_{n\to+\infty}b_{n}^{1}(y)=b^{1}(y)\
\text{exists and $b^{1}(y)>0$}\\},$ (376)

where for any $n\in\mathbb{N}$ and $x,y\in\mathbb{R}^{d}$,
$a_{n}^{1}(x)=a_{n}(x)/a_{n}(x_{1})$ and $b_{n}^{1}(y)=b_{n}(y)a_{n}(x_{1})$,
which is well-defined since for any $n\in\mathbb{N}$, $a_{n}(x_{1})>0$. Note
that $\mathsf{C}_{0}^{0}\cap\mathsf{C}_{0}^{1}=\emptyset$ and
$\mathsf{C}_{1}^{0}\cap\mathsf{C}_{1}^{1}=\emptyset$. Indeed, if there exists
$x\in\mathsf{C}_{0}^{0}\cap\mathsf{C}_{0}^{1}$, then
$a^{0}(x)=\lim_{n\to+\infty}a_{n}(x)/a_{n}(x_{0})>0$ and
$a^{1}(x)=\lim_{n\to+\infty}a_{n}(x)/a_{n}(x_{1})>0$ exists. Therefore
$\lim_{n\to+\infty}a_{n}(x_{1})/a_{n}(x_{0})>0$ exists and
$\lim_{n\to+\infty}b_{n}(y_{1})a_{n}(x_{0})>0$ exists. Hence
$(x_{1},y_{1})\in\mathsf{C}_{0}^{0}\times\mathsf{C}_{1}^{0}$ which is absurd.
Similarly, if there exists $y\in\mathsf{C}_{1}^{0}\cap\mathsf{C}_{1}^{1}$ then
$(x_{1},y_{1})\in\mathsf{C}_{0}^{0}\times\mathsf{C}_{1}^{0}$ which is absurd.
Hence, we consider $T:\mathsf{A}_{b}\to 2^{(\mathbb{R}^{d})^{2}}$ such that
for any $(x,y)\in\mathsf{A}_{b}$,
$T(x,y)=\mathsf{C}_{0}^{(x,y)}\times\mathsf{C}_{1}^{(x,y)}$, where
$\mathsf{C}_{0}^{(x,y)}\times\mathsf{C}_{1}^{(x,y)}$ is constructed as in
(373) replacing $(x_{0},y_{0})$ by $(x,y)$.

Consider a well order on $(\mathsf{A}_{b},\leq)$, which is possible by the
well-ordering principle (Enderton,, 1977, p. 196). For any
$(x,y)\in\mathbb{R}^{d}$, let
$\mathsf{A}_{b}^{(x,y)}=\\{(x^{\prime},y^{\prime})\in(\mathbb{R}^{d})^{2}\,:\;(x^{\prime},y^{\prime})<(x,y)\\}$.
Using the transfinite recursion theorem (Enderton,, 1977, p. 175) there exists
$f:\ \mathsf{A}_{b}\to\\{0,1\\}$ such that for any $(x,y)\in\mathsf{A}_{b}$ if
there exists $(x^{\prime},y^{\prime})\in(\mathbb{R}^{d})^{2}$ such that
$(x^{\prime},y^{\prime})<(x,y)$, $f(x^{\prime},y^{\prime})=1$ and $(x,y)\in
T(x^{\prime},y^{\prime})$ then $f(x,y)=0$ and $f(x,y)=1$ otherwise. Let
$I=f^{-1}(\\{1\\})$. Let $(x,y),(x^{\prime},y)\in I$ with
$(x,y)\neq(x^{\prime},y^{\prime})$ then for $(x,y)<(x^{\prime},y^{\prime})$
for instance. Since $f(x,y)=f(x^{\prime},y^{\prime})=1$ we have that
$(\mathsf{C}_{0}^{(x,y)}\times\mathsf{C}_{1}^{(x,y)})\cap(\mathsf{C}_{0}^{(x^{\prime},y^{\prime})}\times\mathsf{C}_{1}^{(x^{\prime},y^{\prime})})=\emptyset$.
Let $(x,y)\in\mathsf{A}_{b}$. If $f(x,y)=1$ then
$(x,y)\in\mathsf{C}^{(x,y)}_{0}\times\mathsf{C}^{(x,y)}_{1}$. If $f(x,y)=0$
then there exists $(x^{\prime},y^{\prime})<(x,y)$ such that
$(x,y)\in\mathsf{C}^{(x^{\prime},y^{\prime})}_{0}\times\mathsf{C}^{(x^{\prime},y^{\prime})}_{1}$.
Therefore, we get that
$\\{\mathsf{C}^{(x,y)}=(\mathsf{C}_{0}^{(x,y)}\times\mathsf{C}_{1}^{(x,y)})\cap\mathsf{A}_{b}\,:\;(x,y)\in
I\\}$ is a partition of $\mathsf{A}_{b}$.

Since $\mu(\mathsf{A}_{b})\leq 1$, and
$\\{\mathsf{C}^{(x,y)}=(\mathsf{C}_{0}^{(x,y)}\times\mathsf{C}_{1}^{(x,y)})\cap\mathsf{A}_{b}\,:\;(x,y)\in
I\\}$ is a partition of $\mathsf{A}_{b}$, we get that
$J=\\{\mathsf{C}^{(x,y)}\,:\;(x,y)\in
I,\mu_{0}(\mathsf{C}^{(x,y)}_{0})\mu_{1}(\mathsf{C}^{(x,y)}_{1})>0\\}$ is
countable. Denote $\mathsf{A}_{c}=\cup_{(x,y)\in J}\mathsf{C}^{(x,y)}$. Let us
show that
$\mu(\mathsf{A}_{c}^{\mathrm{c}}\cap\mathsf{A}_{b})=\mu(\cup_{(x,y)\in I\cap
J^{\mathrm{c}}}\mathsf{C}^{(x,y)})=0$. Let $x\in\mathbb{R}^{d}$ and define
$\mathsf{D}_{x}=\\{y\in\mathbb{R}^{d}\,:\;(x,y)\in\mathsf{A}_{b}\cap\mathsf{A}_{c}^{\mathrm{c}}\\}$.
If $\mathsf{D}_{x}$ is not empty, then there exists
$(x^{\prime},y^{\prime})\in I$ such that
$x\in\mathsf{C}_{0}^{(x^{\prime},y^{\prime})}$. Then, for any
$y\in\mathsf{D}_{x}$, $y\in\mathsf{C}_{1}^{(x^{\prime},y^{\prime})}$. Hence,
$(x^{\prime},y^{\prime})\in I\cap J^{\mathrm{c}}$ by definition of
$\mathsf{D}_{x}$ and $\mu_{1}(\mathsf{D}_{x})=0$. We get that

$\textstyle{\mu(\mathsf{A}_{b}\cap\mathsf{A}_{c}^{\mathrm{c}})=\int_{\mathbb{R}^{d}}(\int_{\mathsf{D}_{x}}h(x,y)\mathrm{d}\mu_{1}(y))\mathrm{d}\mu_{0}(x)=0,}$
(377)

where $h$ is the density of $\mu$ w.r.t. $\mu_{0}\otimes\mu_{1}$. Note that
this is the only instance in the proof, where we use that $\mu$ is absolutely
continuous w.r.t. $\mu_{0}\otimes\mu_{1}$. For any $(x,y)\in\mathsf{A}_{c}$
define for any $n\in\mathbb{N}$

$\textstyle{\hat{a}_{n}(x)=\sum_{(x^{\prime},y^{\prime})\in
J}\mathbbm{1}_{\mathsf{C}_{0}^{(x^{\prime},y^{\prime})}}(x)a_{n}^{(x^{\prime},y^{\prime})}(x),\quad\hat{b}_{n}(y)=\sum_{(x^{\prime},y^{\prime})\in
J}\mathbbm{1}_{\mathsf{C}_{1}^{(x^{\prime},y^{\prime})}}(x)b_{n}^{(x^{\prime},y^{\prime})}(y).}$
(378)

There exist $\hat{a},\hat{b}:\ \mathbb{R}^{d}\to\left(0,+\infty\right)$ such
that for any $(x,y)\in\mathsf{A}_{c}$,
$\lim_{n\to+\infty}\hat{a}_{n}(x)=\hat{a}(x)$ and
$\lim_{n\to+\infty}\hat{b}_{n}(y)=\hat{b}(y)$. In addition, for any
$(x,y)\in\mathsf{A}_{c}$, $a_{n}(x)b_{n}(y)=\hat{a}_{n}(x)\hat{b}_{n}(y)$.
Hence, for any $(x,y)\in\mathsf{A}_{c}$, $\Phi(x,y)=\hat{a}(x)\hat{b}(y)$.
Since $\mathsf{A}_{a}\cap\mathsf{A}_{c}=\emptyset$ and
$\mu(\mathsf{A}_{c})=\mu(\mathsf{A}_{b})$, we have

$\mu(\mathsf{A}_{a})+\mu(\mathsf{A}_{c})=\mu(\mathsf{A}_{a})+\mu(\mathsf{A}_{b})=\mu(\mathsf{A})=1.$
(379)

We conclude the proof upon remarking that for any $(x,y)\in\mathsf{A}_{a}$,
$\Phi(x,y)=0$ and for any $(x,y)\in\mathsf{A}_{c}$,
$\Phi(x)=\hat{a}(x)\hat{b}(y)$. ∎

In what follows we prove Section F.2.

###### Proof.

Since $\lim_{n\to+\infty}\|\pi^{n}-\pi^{\infty}\|_{\mathrm{TV}}=0$, there
exist $\mathsf{A}$ with $\mu(\mathsf{A})=1$ and $\Phi:\
(\mathbb{R}^{d})^{2}\to\left[0,+\infty\right)$ such that, up to extraction,
for any $x,y\in\mathsf{A}$

$\lim_{n\to+\infty}a_{n}(x)b_{n}(y)=\Phi(x,y),$ (380)

and $(\mathrm{d}\pi^{\infty}/\mathrm{d}\mu)=\Phi$. Using Section F.2, there
exist $a,b:\ \mathbb{R}^{d}\to\left[0,+\infty\right)$ and $\mathsf{B}$ with
$\pi^{\infty}(\mathsf{B})=1$ such that for any $x,y\in\mathsf{B}$,
$(\mathrm{d}\pi^{\infty}/\mathrm{d}\mu)(x,y)=a(x)b(y)$. Since $\mu$ is
absolutely continuous w.r.t. $\pi^{\infty}$, we get that for any
$x,y\in\mathbb{R}^{d}$,
$(\mathrm{d}\pi^{\infty}/\mathrm{d}(\mu_{0}\otimes\mu_{1}))(x,y)=a(x)b(y)h(x,y)$.
In addition, the Schrödinger bridge
$\pi^{\star}\in\mathscr{P}((\mathbb{R}^{d})^{2})$ exists, see (Rüschendorf and
Thomsen,, 1993, Theorem 3), and there exist $a^{\prime},b^{\prime}:\
\mathbb{R}^{d}\to\left[0,+\infty\right)$ and $\mathsf{B}^{\prime}$ with
$\mu(\mathsf{B}^{\prime})=1$ such that for any $x,y\in\mathsf{B}^{\prime}$

$(\mathrm{d}\pi^{\star}/\mathrm{d}(\mu_{0}\otimes\mu_{1}))(x,y)=a^{\prime}(x)b^{\prime}(y)h(x,y).$
(381)

Let $\mathscr{M}_{+,\times}$ be the space of non-negative product measures
over $\mathcal{B}(\mathbb{R}^{d})\otimes\mathcal{B}(\mathbb{R}^{d})$. Let
$\mathbf{\Psi}_{\bar{h}}:\ \mathscr{M}_{+,\times}\to\mathscr{M}_{+,\times}$ be
given for any $\lambda=\lambda_{0}\otimes\lambda_{1}\in\mathscr{M}_{+,\times}$
by $\mathbf{\Psi}_{\bar{h}}(\lambda)=\Psi_{h}^{\lambda}$ where for any
$\mathsf{A},\mathsf{B}\in\mathcal{B}(\mathbb{R}^{d})$

$\textstyle{\Psi_{h}^{\lambda}(\mathsf{A}\times\mathsf{B})=(\int_{\mathsf{A}\times\mathbb{R}^{d}}\bar{h}(x,y)\mathrm{d}\lambda_{0}(x)\mathrm{d}\lambda_{1}(x))(\int_{\mathbb{R}^{d}\times\mathsf{B}}\bar{h}(x,y)\mathrm{d}\lambda_{0}(x)\mathrm{d}\lambda_{1}(y))}$
(382)

where for any $x,y\in\mathbb{R}^{d}$,
$\bar{h}(x,y)=h(x,y)\Phi_{0}^{-1}(x)\Phi_{1}^{-1}(y)$. Note that
$\bar{h}\in\mathrm{C}(\mathbb{R}^{d}\times\mathbb{R}^{d},\left[0,+\infty\right))$
and is bounded. Hence, using (Beurling,, 1960, Theorem 2) and (370) we get
that $\mathbf{\Psi}_{\bar{h}}$ is a bijection. Let
$\lambda=(a\Phi_{0}\mu_{0},b\Phi_{1}\mu_{1})$ and
$\lambda^{\prime}=(a^{\prime}\Phi_{0}\mu_{0},b^{\prime}\Phi_{1}\mu_{1})$.
Then, since $\pi^{\star}_{i}=\pi^{\infty}_{i}=\nu_{i}$ for $i\in\\{0,1\\}$ we
get that $\mathbf{\Psi}_{h}(\lambda)=\mathbf{\Psi}_{h}(\lambda^{\prime})$.
Hence $\lambda=\lambda^{\prime}$ and $\pi^{\infty}=\pi^{\star}$ which
concludes the proof. ∎

In Section F.2 we derive an alternative proposition to Section F.2. We start
with the following lemma.

######  Lemma .

Let $\pi^{\star}\in\mathscr{P}_{2}$ with $\pi^{\star}_{i}=\nu_{i}$ for
$i\in\\{0,1\\}$. Assume that $\operatorname{KL}(\pi^{\star}|\mu)<+\infty$ and
that $\mathrm{L}^{1}(\nu_{0})\oplus\mathrm{L}^{1}(\nu_{1})$ is closed in
$\mathrm{L}^{1}(\pi^{\star})$. In addition, assume that there exist $a,b:\
\mathbb{R}^{d}\to\left[0,+\infty\right)$ and $\mathsf{A}$ with
$\pi^{\star}(\mathsf{A})=1$ such that for any $(x,y)\in\mathsf{A}$,

$(\mathrm{d}\pi^{\star}/\mathrm{d}\mu)(x,y)=a(x)b(y).$ (383)

Then $\pi^{\star}$ is the Schrödinger bridge.

###### Proof.

Since $\operatorname{KL}(\pi^{\star}|\mu)<+\infty$ we have that

$\textstyle{\int_{(\mathbb{R}^{d})^{2}}\left|\log(a(x)b(y))\right|\mathrm{d}\pi^{\star}(x,y)<+\infty.}$
(384)

Using (Kober,, 1939, Theorem 1) and that $\pi^{\star}_{i}=\nu_{i}$ for
$i\in\\{0,1\\}$, we get that

$\textstyle{\int_{\mathbb{R}^{d}}\left|\log
a(x)\right|\mathrm{d}\nu_{0}(x)+\int_{\mathbb{R}^{d}}\left|\log
b(y)\right|\mathrm{d}\nu_{1}(y)<+\infty.}$ (385)

Let $\pi\in\mathscr{P}_{2}$ such that $\pi_{i}=\nu_{i}$ for $i\in\\{1,2\\}$
and $\operatorname{KL}(\pi|\mu)<+\infty$. Using (385), we have that
$\int_{(\mathbb{R}^{d})^{2}}\left|\log((\mathrm{d}\pi^{\star}/\mathrm{d}\mu)(x,y))\right|\mathrm{d}\pi(x,y)<+\infty$.
Hence, $(\mathrm{d}\pi^{\star}/\mathrm{d}\mu)>0$, $\pi$-almost surely. Using
this result we have for any $\mathsf{A}\in\mathcal{B}(\mathbb{R}^{d})$

$\displaystyle\pi(\mathsf{A})$
$\displaystyle=\textstyle{\int_{\mathbb{R}^{d}}\mathbbm{1}_{\mathsf{A}}(x)(\mathrm{d}\pi^{\star}/\mathrm{d}\mu)(x)(\mathrm{d}\pi^{\star}/\mathrm{d}\mu)(x)^{-1}\mathrm{d}\pi(x)}$
(386)
$\displaystyle=\textstyle{\int_{\mathbb{R}^{d}}\mathbbm{1}_{\mathsf{A}}(x)(\mathrm{d}\pi^{\star}/\mathrm{d}\mu)(x)(\mathrm{d}\pi^{\star}/\mathrm{d}\mu)(x)^{-1}(\mathrm{d}\pi/\mathrm{d}\mu)(x)\mathrm{d}\mu(x)}$
(387)
$\displaystyle=\textstyle{\int_{\mathbb{R}^{d}}\mathbbm{1}_{\mathsf{A}}(x)(\mathrm{d}\pi^{\star}/\mathrm{d}\mu)(x)^{-1}(\mathrm{d}\pi/\mathrm{d}\mu)(x)\mathrm{d}\pi^{\star}(x)}.$
(388)

Hence we get that
$\mathrm{d}\pi/\mathrm{d}\pi^{\star}=(\mathrm{d}\pi/\mathrm{d}\mu)(\mathrm{d}\pi^{\star}/\mathrm{d}\mu)^{-1}$.
In addition, we have that

$\textstyle{\operatorname{KL}(\pi^{\star}|\mu)=\int_{\mathbb{R}^{d}}\log(a(x))\mathrm{d}\nu_{0}(x)+\int_{\mathbb{R}^{d}}\log(b(y))\mathrm{d}\nu_{1}(y)=\int_{(\mathbb{R}^{d})^{2}}\log((\mathrm{d}\pi^{\star}/\mathrm{d}\mu)(x,y))\mathrm{d}\pi(x,y).}$
(389)

We get that

$\textstyle{\operatorname{KL}(\pi|\pi^{\star})=\int_{\mathbb{R}^{d}}\log((\mathrm{d}\pi/\mathrm{d}\mu)(\mathrm{d}\pi^{\star}/\mathrm{d}\mu)(x,y)^{-1})\mathrm{d}\pi(x,y)=\operatorname{KL}(\pi|\mu)-\operatorname{KL}(\pi^{\star}|\mu).}$
(390)

Hence, $\operatorname{KL}(\pi|\mu)\geq\operatorname{KL}(\pi^{\star}|\mu)$ with
equality if and only if $\pi^{\star}=\pi$. Therefore, $\pi^{\star}$ is the
Schrödinger bridge. ∎

The following proposition is an alternative to Section F.2.

######  Proposition .

Assume B 1. Then there exists a solution $\pi^{\star}$ to the Schrödinger
bridge. Assume that the IPF sequence $(\pi^{n})_{n\in\mathbb{N}}$ satisfies
$\lim_{n\to+\infty}\|\pi^{n}-\pi^{\infty}\|_{\mathrm{TV}}=0$ with
$\pi^{\infty}\in\mathscr{P}_{2}$. If
$\mathrm{L}^{1}(\nu_{0})\oplus\mathrm{L}^{1}(\nu_{1})$ is closed in
$\mathrm{L}^{1}(\pi^{\infty})$ then $\pi^{\infty}=\pi^{\star}$.

###### Proof.

Since $\lim_{n\to+\infty}\|\pi^{n}-\pi^{\infty}\|_{\mathrm{TV}}=0$ there exist
$\mathsf{A}$ with $\mu(\mathsf{A})=1$ and $\Phi:\
(\mathbb{R}^{d})^{2}\to\left[0,+\infty\right)$ such that, up to extraction,
for any $x,y\in\mathsf{A}$

$\lim_{n\to+\infty}a_{n}(x)b_{n}(y)=\Phi(x,y),$ (391)

and $(\mathrm{d}\pi^{\infty}/\mathrm{d}\mu)=\Phi$. Using Section F.2, there
exist $a,b:\ \mathbb{R}^{d}\to\left[0,+\infty\right)$ and $\mathsf{B}$ with
$\pi^{\infty}(\mathsf{B})=1$ such that for any $x,y\in\mathsf{B}$,
$(\mathrm{d}\pi^{\infty}/\mathrm{d}\mu)(x,y)=a(x)b(y)$. We conclude upon using
Section F.2. ∎

##  Appendix G Geometric convergence rates and convergence to ground-truth

In this section, we derive geometric convergence rates in Section G.1 in a
Gaussian setting. In particular, we provide an explicit upper-bound on the
convergence rate that depends only on the covariance of the reference measure
and the target. In Section G.2, we show that DSB (with Brownian reference
measure) converges towards the Schrödinger bridge in a Gaussian setting where
the ground-truth is available. In Section 4 we show that our implementation
actually recovers the Schrödinger bridge in this setting.

###  G.1 Geometric convergence rates

In the following proposition we show that we recover a geometric convergence
rate in a Gaussian setting and derive intuition from this case study. We set
$N=1$ and assume that for any $x_{0},x_{N}\in\mathbb{R}^{d}$ we have

$p(x_{0},x_{N})\propto\exp[-\left\|x_{0}\right\|^{2}+2\alpha\langle
x_{0},x_{N}\rangle-\left\|x_{N}\right\|^{2}],$ (392)

with $\alpha\in\left[0,1\right)$. In this case assume that there exists
$\beta>0$ such that the target marginals are given for any
$x_{0},x_{N}\in\mathbb{R}^{d}$ by

$p_{\textup{data}}(x_{0})\propto\exp[-\beta\left\|x_{0}\right\|^{2}],\qquad
p_{\textup{prior}}(x_{N})\propto\exp[-\beta\left\|x_{N}\right\|^{2}].$ (393)

######  Proposition .

Let $\alpha\in\left(0,1\right)$ and $\beta>0$. Then the Schrödinger bridge
$\pi^{\star}$ exists and there exists $C\geq 0$ (explicit in the proof) such
that for any $n\in\mathbb{N}$, $\operatorname{KL}(\pi^{\star}|\pi^{n})\leq
C\kappa^{2n}$, with $\kappa<1$ given by $\kappa=\rho/(1+\rho)$ and
$\rho=2\alpha/\beta^{2}$. In addition, $\pi^{\star}$ admits a density w.r.t.
the Lebesgue measure denoted $p^{\star}$ and given for any
$x,y\in\mathbb{R}^{d}$ by

$\textstyle{p^{\star}(x,y)=\exp[-\gamma^{\star}\|x\|^{2}+2\alpha\langle
x,y\rangle-\gamma^{\star}\|y\|^{2}]/\int_{\mathbb{R}^{d}}\exp[-\gamma^{\star}\|x\|^{2}+2\alpha\langle
x,y\rangle-\gamma^{\star}\|y\|^{2}]\mathrm{d}x\mathrm{d}y,}$ (394)

with $\gamma^{\star}=(\beta^{2}/2)(1+(1+4\alpha^{2}/\beta^{2})^{1/2})$.

Remark that if $\beta^{2}=1-\alpha^{2}$ then $\gamma^{\star}$ and
$p^{\star}=p$, i.e. the IPF leaves $\mu$ invariant. Note that the performance
of the IPF improves if $\kappa$ is close to $0$, i.e. if
$\rho=2\alpha/\beta^{2}$ is close to $0$. This is the case if $\alpha\approx
0$ (the marginals are almost independent) or if $\beta\approx+\infty$ (the
target distribution is close to $\updelta_{0}$), see Figure 8. This behavior
is in accordance with the limit case where the marginals are independent or
one of the target distribution is a Dirac mass in which case the IPF converges
in two iterations.

Figure 8: Evolution of $\kappa^{2}$ depending on $\alpha$ and $\beta$.

Also, note that the convergence rate does not depend on the dimension but only
on the constants of the problem. In what follows we first derive the IPF
sequence for this Gaussian problem and establish that $\alpha$ controls the
amount of information shared by the marginals. Then we prove Section G.1. In
the rest of this section, we let $\mu\in\mathscr{P}_{2}$ with density $p$
w.r.t. the Lebesgue measure such that for any $x_{0},x_{1}\in\mathbb{R}^{d}$

$\textstyle{p(x_{0},x_{1})=\exp[-\left\|x_{0}\right\|^{2}+2\alpha\langle
x_{0},x_{1}\rangle-\left\|x_{1}\right\|^{2}]/\int_{\mathbb{R}^{d}}\exp[-\left\|x_{0}\right\|^{2}+2\alpha\langle
x_{0},x_{1}\rangle-\left\|x_{1}\right\|^{2}]\mathrm{d}x_{0}\mathrm{d}x_{1}.}$
(395)

We have that $\mu$ is the Gaussian distribution with zero mean and covariance
matrix $\Sigma$ such that

$\textstyle{\Sigma=(2(1-\alpha^{2}))^{-1}\left(\begin{matrix}\operatorname{Id}&\alpha\operatorname{Id}\\\
\alpha\operatorname{Id}&\operatorname{Id}\end{matrix}\right).}$ (396)

We have that $\det(\Sigma)=2^{2d}(1-\alpha^{2})^{-d}$ using Schur complement
(Petersen et al.,, 2008, Section 9.1.2). Hence we get that for any
$x_{0},x_{1}\in\mathbb{R}^{d}$

$\textstyle{p(x_{0},x_{1})=\uppi^{-d}(1-\alpha^{2})^{d/2}\exp[-\left\|x_{0}\right\|^{2}+2\alpha\langle
x_{0},x_{1}\rangle-\left\|x_{1}\right\|^{2}].}$ (397)

In what follows, we denote $C=\uppi^{d}(1-\alpha^{2})^{-d/2}$. Similarly, we
get that $\mu_{0}=\mu_{1}$ and that they admit the density $p_{0}$ w.r.t. the
Lebesgue measure given for any $x\in\mathbb{R}^{d}$ by

$p_{0}(x)=\uppi^{-d/2}(1-\alpha^{2})^{d/2}\exp[-\left\|x\right\|^{2}(1-\alpha^{2})].$
(398)

In what follows, we denote $C_{0}=\uppi^{d/2}(1-\alpha^{2})^{-d/2}$. In this
case note that $\mu$ admits a density w.r.t. $\mu_{0}\otimes\mu_{1}$ given for
any $x_{0},x_{1}\in\mathbb{R}^{d}$ by

$h(x_{0},x_{1})=(\mathrm{d}\mu/\mathrm{d}(\mu_{0}\otimes\mu_{1}))(x_{0},x_{1})=(1-\alpha^{2})^{-d/2}\exp[-\alpha^{2}\left\|x_{0}\right\|^{2}-2\alpha\langle
x_{0},x_{1}\rangle-\alpha^{2}\left\|x_{1}\right\|^{2}].$ (399)

Remark that $p_{\textup{prior}}=p_{\textup{data}}=q$ with for any
$x\in\mathbb{R}^{d}$,
$q(x)=\uppi^{-d/2}\beta^{d/2}\exp[-\beta\left\|x\right\|^{2}]$. We have for
any $x_{1},x_{0}\in\mathbb{R}^{d}$

$p_{1|0}(x_{1}|x_{0})=p(x_{0},x_{1})/p_{0}(x_{0})=\uppi^{-d/2}(1-\alpha^{2})^{d/2}\exp[-\alpha^{2}\left\|x_{0}\right\|^{2}+2\alpha\langle
x_{0},x_{1}\rangle-\left\|x_{1}\right\|^{2}].$ (400)

Hence, we have that 1 holds and the IPF sequence is well-defined and converges
using Section 3.4. In what follows we start to show that $\alpha$ controls the
amount of information shared by the two marginals $\mu_{0}$ and $\mu_{1}$,
i.e. the mutual information. More precisely we have the following result.

######  Proposition .

For any $\alpha\in\left(0,1\right)$ we have
$\operatorname{KL}(\mu|\mu_{0}\otimes\mu_{1})=-(d/2)\log(1-\alpha^{2})$.

###### Proof.

For any $x,y\in\mathbb{R}^{d}$ we have

$(\mathrm{d}\mu/(\mathrm{d}\mu_{0}\otimes\mathrm{d}\mu_{1}))(x,y)=\exp[-\alpha^{2}\|x\|^{2}+2\alpha\langle
x,y\rangle-\alpha^{2}\|y\|^{2}](1-\alpha^{2})^{-d/2}.$ (401)

We have that

$\textstyle{\int_{\mathbb{R}^{d}\times\mathbb{R}^{d}}(-\alpha^{2}\left\|x\right\|^{2}-\alpha^{2}\left\|y\right\|^{2}+2\alpha\langle
x,y\rangle)\mathrm{d}\mu(x,y)=0.}$ (402)

Hence,
$\operatorname{KL}(\mu|\mu_{0}\otimes\mu_{1})=-(d/2)\log(1-\alpha^{2})$, which
concludes the proof. ∎

In what follows, we denote by $(\pi^{n})_{n\in\mathbb{N}}$ the IPFP sequence,
defined for any $n\in\mathbb{N}$ we have for any $x,y\in\mathbb{R}^{d}$

$\textstyle{(\mathrm{d}\pi^{2n}/\mathrm{d}\mu)(x,y)=a_{n}(x)b_{n}(y)h(x,y),\qquad(\mathrm{d}\pi^{2n+1}/\mathrm{d}\mu)(x,y)=a_{n+1}(x)b_{n}(y)h(x,y),}$
(403)

where for any $x,y\in\mathbb{R}^{d}$

$\displaystyle\textstyle{a_{n+1}(x)=(\mathrm{d}\nu_{0}/\mathrm{d}\mu_{0})(x)\left(\int_{\mathbb{R}^{d}}h(x,y)b_{n}(y)\mathrm{d}\mu_{1}(y)\right)^{-1},}$
(404)
$\displaystyle\textstyle{b_{n+1}(x)=(\mathrm{d}\nu_{1}/\mathrm{d}\mu_{1})(y)\left(\int_{\mathbb{R}^{d}}h(x,y)a_{n+1}(x)\mathrm{d}\mu_{0}(x)\right)^{-1}.}$
(405)

We now turn to the proof of the Section G.1.

###### Proof.

Let $\alpha\in\left(0,1\right)$ and $\beta>1$. We have for any
$x,y\in\mathbb{R}^{d}$

$(\mathrm{d}\nu_{0}/\mathrm{d}\mu_{0})(x)=\exp[(1-\beta^{2}-\alpha^{2})\|x\|^{2}]/C_{2},\qquad(\mathrm{d}\nu_{1}/\mathrm{d}\mu_{1})(y)=\exp[(1-\beta^{2}-\alpha^{2})\|y\|^{2}]/C_{2},$
(406)

with $C_{2}=C_{1}/C_{0}$ with $C_{1}=\uppi^{d/2}\beta^{d/2}$. For any
$x\in\mathbb{R}^{d}$ and $\gamma\geq 0$ we have

$\displaystyle\textstyle{(\mathrm{d}\nu_{0}/\mathrm{d}\mu_{0})(x)\left(\int_{\mathbb{R}^{d}}\exp[-\gamma\left\|y\right\|^{2}]h(x,y)\mathrm{d}\mu_{1}(y)\right)^{-1}}$
(407)
$\displaystyle\qquad\textstyle{=(C_{0}C_{2})^{-1}C\exp[(1-\beta^{2}-\alpha^{2})\left\|x\right\|^{2}]\left(\int_{\mathbb{R}^{d}}\exp[-\gamma\left\|y\right\|^{2}-\left\|y-\alpha
x\right\|^{2}]\mathrm{d}y\right)}^{-1}$ (408)
$\displaystyle\qquad=(C_{0}C_{2})^{-1}C\exp[(1-\beta^{2}-\alpha^{2})\left\|x\right\|^{2}]$
(409)
$\displaystyle\qquad\qquad\textstyle{\times\left(\int_{\mathbb{R}^{d}}\exp[-(\gamma+1)\left\|y-\alpha/(\gamma+1)x\right\|^{2}-\alpha^{2}(1-1/(\gamma+1))\left\|x\right\|^{2}]\mathrm{d}y\right)^{-1}}$
(410)
$\displaystyle\qquad=(C_{0}C_{2})^{-1}C\exp[(1-\beta^{2}-\alpha^{2}+\alpha^{2}\gamma/(\gamma+1))\left\|x\right\|^{2}]$
(411)
$\displaystyle\qquad\qquad\textstyle{\times\left(\int_{\mathbb{R}^{d}}\exp[-(\gamma+1)\left\|y-\alpha/(\gamma+1)x\right\|^{2}]\mathrm{d}y\right)^{-1}}$
(412)
$\displaystyle\qquad=(C_{0}C_{2}\tilde{C}_{\gamma})^{-1}C\exp[(1-\beta^{2}-\alpha^{2}/(\gamma+1))\left\|x\right\|^{2}],$
(413)

with $\tilde{C}_{\gamma}=\pi^{d/2}(1+\gamma)^{-d/2}$. Note that
$a_{0}=b_{0}=1$. Let $n\in\mathbb{N}$ and assume that for any
$y\in\mathbb{R}^{d}$ $b_{n}(y)=\exp[-\gamma_{2n}\left\|y\right\|^{2}]/C_{2n}$
with $\gamma_{2n}\geq 0$ and $C_{2n}>0$ then we have for any
$x\in\mathbb{R}^{d}$

$a_{n+1}(x)=(C_{0}C_{2}\tilde{C}_{\gamma_{2n}})^{-1}CC_{2n}\exp[-(1-\beta^{2}-\alpha^{2}/(\gamma_{2n}+1))\left\|x\right\|^{2}]=\exp[-\gamma_{2n+1}\left\|x\right\|^{2}]/C_{2n+1},$
(414)

with

$\gamma_{2n+1}=\beta^{2}-1+\alpha^{2}/(\gamma_{2n}+1),\qquad(C_{0}C_{2}\tilde{C}_{\gamma_{2n}})/(CC_{2n})=C_{2n+1}.$
(415)

Similarly, if we assume that for any $x\in\mathbb{R}^{d}$
$a_{n+1}(x)=\exp[-\gamma_{2n+1}\left\|x\right\|^{2}]/C_{2n+1}$ with
$\gamma_{2n+1}\geq 0$ and $C_{2n+1}>0$ then we have for any
$y\in\mathbb{R}^{d}$

$\displaystyle b_{n+1}(y)$
$\displaystyle=(C_{0}C_{2}\tilde{C}_{\gamma_{2n+1}})^{-1}(CC_{2n+1})\exp[-(1-\beta^{2}-\alpha^{2}/(\gamma_{2n+1}+1))\left\|y\right\|^{2}]$
(416) $\displaystyle=\exp[-\gamma_{2n+2}\left\|y\right\|^{2}]/C_{2n+2},$ (417)

with

$\gamma_{2n+2}=\beta^{2}-1+\alpha^{2}/(\gamma_{2n+1}+1),\qquad(C_{0}C_{2}\tilde{C}_{\gamma_{2n+1}})/(CC_{2n+1})=C_{2n+2}.$
(418)

Combining this result, (415) and using the recursion principle we get that for
any $n\in\mathbb{N}$

$a_{n+1}(x)=\exp[-\gamma_{2n+1}\left\|x\right\|^{2}]/C_{2n+1},\qquad
b_{n+1}(y)=\exp[-\gamma_{2n+2}\left\|y\right\|^{2}]/C_{2n+2}.$ (419)

The recursion can be extended to $a_{0}$ and $b_{0}$ by setting
$\gamma_{-1}=\gamma_{0}=0$ and $C_{-1}=C_{0}=1$. Therefore, for any
$n\in\mathbb{N}$ we have

$\gamma_{n+1}=\beta^{2}-1+\alpha^{2}/(\gamma_{n}+1).$ (420)

We now study the convergence of the sequence $(\gamma_{n})_{n\in\mathbb{N}}$.
By recursion, we have that for any $k,\ell\in\mathbb{N}$, if
$\gamma_{k}\geq\gamma_{\ell}$ then for any $m\in\mathbb{N}$ with $m$ even we
have $\gamma_{m+k}\geq\gamma_{m+\ell}$ and for any $m\in\mathbb{N}$ with $m$
odd we have $\gamma_{m+k}\leq\gamma_{m+\ell}$. We have $\gamma_{0}=0$ and

$\gamma_{1}=\beta^{2}+\alpha^{2}-1,\qquad\gamma_{2}=\beta^{2}-1+\alpha^{2}/(\beta^{2}+\alpha^{2}).$
(421)

We divide the rest of the proof into three parts.

  1. (a)

First assume that $\beta^{2}>1-\alpha^{2}$. Using (421) we have that
$\gamma_{1}>\gamma_{0}$ and $\gamma_{2}>\gamma_{0}$. Therefore, we obtain that
$(\gamma_{2n})_{n\in\mathbb{N}}$ is non-decreasing, that
$(\gamma_{2n+1})_{n\in\mathbb{N}}$ is non-increasing and that for any
$n\in\mathbb{N}$, $0\leq\gamma_{2n}\leq\gamma_{2n+1}\leq\gamma_{1}$.
Therefore, $(\gamma_{n})_{n\in\mathbb{N}}$ converges and we denote
$\gamma^{\star}$ its limit. We have
$\gamma^{\star}=\beta^{2}-1+\alpha^{2}/(\gamma^{\star}+1)$. Hence,
$\gamma^{\star}$ is a root of $X^{2}+(2-\beta^{2})X+1-\alpha^{2}-\beta^{2}$.
We get that $\gamma^{\star}=\gamma_{0}^{\star}$ or
$\gamma^{\star}=\gamma_{1}^{\star}$ with

$\gamma_{0}^{\star}=\beta^{2}/2-1-(1/2)(\beta^{4}+4\alpha^{2})^{1/2},\qquad\gamma_{1}^{\star}=\beta^{2}/2-1+(1/2)(\beta^{4}+4\alpha^{2})^{1/2},$
(422)

$\gamma_{0}^{\star},\gamma_{1}^{\star}$ are non-decreasing function of
$\beta$. We get that for any $\beta\geq 0$ such that $\beta^{2}\geq
1-\alpha^{2}$, $\gamma_{0}^{\star}\leq 0$. In addition, we have
$\gamma_{1}^{\star}=0$ for $\beta^{2}=1-\alpha^{2}$, hence for any $\beta\geq
0$ such that $\beta^{2}\geq 1-\alpha^{2}$, $\gamma_{1}^{\star}\geq 0$. Since
$\gamma^{\star}\geq 0$ we have

$\gamma^{\star}=-1+\beta^{2}/2+(1/2)(\beta^{4}+4\alpha^{2})^{1/2}.$ (423)

For any $n\in\mathbb{N}$, denote $\xi_{n}=\gamma_{n}-\gamma^{\star}$ and
$\tau=\gamma^{\star}+1$. Let $\varepsilon>0$. Since
$\lim_{n\to+\infty}\xi_{n}=0$, there exists $n_{0}\in\mathbb{N}$ such that
$\left|\xi_{n}\right|/\tau\leq\varepsilon$. Using (420), we obtain that for
any $n\in\mathbb{N}$

$\displaystyle\textstyle{|\xi_{n+1}|=\alpha^{2}|1/(\gamma_{n}+1)-\tau^{-1}|=(\alpha^{2}/\tau)|1-(\xi_{n}/\tau+1)^{-1}|\leq(\alpha/\tau)^{2}|\xi_{n}|/(1-\varepsilon).}$
(424)

Hence, we get that for any $\varepsilon\in\left(0,1\right)$, there exists
$C_{\varepsilon}>0$ such that for any $n\in\mathbb{N}$

$\left|\xi_{n}\right|\leq
C_{\varepsilon}\kappa^{n},\qquad\kappa=(\alpha/(\tau(1-\varepsilon)^{1/2}))^{2}.$
(425)

Note that $\tau>\alpha$ using (423) and $\kappa\in\left(0,1\right)$ if
$\varepsilon<1-\alpha/\tau$.

For any $n\in\mathbb{N}$ and $x,y\in\mathbb{R}^{d}$ we have

$\displaystyle\Phi_{n}(x,y)$
$\displaystyle=a_{n+1}(x)b_{n+1}(y)=\exp[-\gamma_{2n+1}\left\|x\right\|^{2}-\gamma_{2n+2}\left\|y\right\|^{2}]/(C_{2n+1}C_{2n+2})$
(426)
$\displaystyle=\exp[-\gamma_{2n+1}\left\|x\right\|^{2}-\gamma_{2n+2}\left\|y\right\|^{2}]/(\tilde{C}\tilde{C}_{\gamma_{2n+1}}),$
(427)

with $\tilde{C}=C_{0}C_{2}/C$. Therefore we obtain that for any
$x,y\in\mathbb{R}^{d}$, $\Phi^{\star}(x,y)=\lim_{n\to+\infty}\Phi_{n}(x,y)$
exists and we have

$\Phi^{\star}(x,y)=\exp[-\gamma^{\star}\left\|x\right\|^{2}-\gamma^{\star}\left\|y\right\|^{2}]/(\tilde{C}\tilde{C}_{\gamma^{\star}}).$
(428)

Using this result we get that for any $x,y\in\mathbb{R}^{d}$

$\displaystyle(\mathrm{d}\pi^{2n}/\mathrm{d}\pi^{\star})(x,y)$
$\displaystyle=\exp[-\xi_{2n+1}\left\|x\right\|^{2}-\xi_{2n+2}\left\|y\right\|^{2}]C_{\gamma^{\star}}/C_{\gamma_{2n+1}}$
(429)
$\displaystyle=\exp[-\xi_{2n+1}\left\|x\right\|^{2}-\xi_{2n+2}\left\|y\right\|^{2}]\left\\{(1+\gamma_{2n+1})/(1+\gamma^{\star})\right\\}^{-d/2}$
(430)
$\displaystyle=\exp[-\xi_{2n+1}\left\|x\right\|^{2}-\xi_{2n+2}\left\|y\right\|^{2}]\left\\{1+\xi_{2n+1}/(1+\gamma^{\star})\right\\}^{-d/2}.$
(431)

Therefore we have for any $x,y\in\mathbb{R}^{d}$

$\displaystyle\log\left((\mathrm{d}\pi^{2n}/\mathrm{d}\pi^{\star})(x,y)\right)$
$\displaystyle\leq\left|\xi_{2n+1}\right|\left\|x\right\|^{2}+\left|\xi_{2n+2}\right|\left\|y\right\|^{2}+(d/2)\left|\log\left(1+\xi_{2n+1}/(1+\gamma^{\star})\right)\right|$
(432)
$\displaystyle\leq\left|\xi_{2n+1}\right|\left\|x\right\|^{2}+\left|\xi_{2n+2}\right|\left\|y\right\|^{2}+(d/2)\left|\xi_{2n+1}\right|.$
(433)

Therefore we obtain that for any $n\in\mathbb{N}$

$\operatorname{KL}(\pi^{\star}|\pi^{n})\leq(d/2)(\beta^{-2}\left|\xi_{2n+1}\right|+\beta^{-2}\left|\xi_{2n+2}\right|+\left|\xi_{2n+1}\right|).$
(434)

A similar inequality holds for $\operatorname{KL}(\pi^{\star}|\pi^{n})$.
Therefore we get that for any $\varepsilon\in\left(0,1-\alpha/\tau\right)$
there exists $C_{\varepsilon}\geq 0$ such that for any $n\in\mathbb{N}$ we
have

$\operatorname{KL}(\pi^{\star}|\pi^{n})\leq
C_{\varepsilon}\kappa_{\varepsilon}^{2n},$ (435)

with

$\displaystyle\kappa_{\varepsilon}$
$\displaystyle=\alpha/(\tau(1-\varepsilon)^{1/2})=(2\alpha)/((\beta^{2}+(\beta^{4}+4\alpha^{2})^{1/2})(1-\varepsilon)^{1/2})$
(436) $\displaystyle\leq\rho/((1+(1+\rho^{2})^{1/2})(1-\varepsilon)^{1/2}).$
(437)

Let $\varepsilon<1-(1+\rho)/(1+(1+\rho^{2})^{1/2})$. Then we get that
$\kappa_{\varepsilon}\leq\kappa$ which concludes the first part of the proof.

  2. (b)

If $\beta^{2}=1-\alpha^{2}$ then the IPF is stationary since the IPF leaves
$\mu$ invariant.

  3. (c)

Finally we assume that $\beta^{2}<1-\alpha^{2}$. Using (421) we have that
$\gamma_{1}<\gamma_{0}$ and $\gamma_{2}<\gamma_{0}$ since
$\beta^{2}<1-\alpha^{2}$. Therefore, we obtain that
$(\gamma_{2n})_{n\in\mathbb{N}}$ is non-increasing, that
$(\gamma_{2n+1})_{n\in\mathbb{N}}$ is non-decreasing and that for any
$n\in\mathbb{N}$, $0\geq\gamma_{2n}\geq\gamma_{2n+1}\geq\gamma_{1}$.
Therefore, $(\gamma_{n})_{n\in\mathbb{N}}$ converges and we denote
$\gamma^{\star}$ its limit. We have
$\gamma^{\star}=\beta^{2}-1+\alpha^{2}/(\gamma^{\star}+1)$. Hence,
$\gamma^{\star}$ is a root of $X^{2}+(2-\beta^{2})X+1-\alpha^{2}-\beta^{2}$.
We recall that the two roots of this polynomial are given by

$\gamma_{0}^{\star}=\beta^{2}/2-1-(1/2)(\beta^{4}+4\alpha^{2})^{1/2},\qquad\gamma_{1}^{\star}=\beta^{2}/2-1+(1/2)(\beta^{4}+4\alpha^{2})^{1/2}.$
(438)

We have

$\displaystyle\gamma_{1}-\gamma_{0}^{\star}$
$\displaystyle=\textstyle{\beta^{2}+\alpha^{2}-1-\beta^{2}/2+1-(1/2)(\beta^{4}+4\alpha^{2})^{1/2}}$
(439)
$\displaystyle=(1/2)(\beta^{2}+2\alpha^{2}-(\beta^{4}+4\alpha^{2})^{1/2})\geq
0.$ (440)

Since $\gamma_{3}>\gamma_{1}$ we get that for any $n\in\mathbb{N}$ with $n\geq
3$, $\gamma_{n}\geq\gamma_{3}>\gamma_{0}^{\star}$. Therefore
$\gamma^{\star}>\gamma_{0}^{\star}$ and then
$\gamma^{\star}=\gamma_{1}^{\star}$. The rest of the proof is similar to the
case where $\beta^{2}>1-\alpha^{2}$.

∎

###  G.2 Convergence to ground-truth

In this section, we provide an analytic form for the Schrödinger bridge in a
Gaussian context. Let $\nu_{0}$ be the $d$ dimensional Gaussian distribution
with mean $-a$ (with $a\in\mathbb{R}^{d}$) and covariance matrix
$\mathbf{I}\in\mathbb{R}^{d\times d}$. Similarly, let $\nu_{1}$ be the one-
dimensional Gaussian distribution with mean $a$ and covariance matrix
$\mathbf{I}$. We consider the reference distribution $\pi^{0}$ such that
$\pi^{0}_{0}=\nu_{0}$ and for any $x,y\in\mathbb{R}^{d}$

$\textstyle{(\mathrm{d}\pi_{1|0}^{0}/\mathrm{d}\lambda)(x,y)=(2\uppi)^{-d/2}\exp[-\|x-y\|^{2}/2],}$
(441)

where $\lambda$ denotes the Lebesgue measure on $\mathbb{R}$. Note that
$\pi_{1|0}^{0}$ can be obtained by running a $d$-dimensional Brownian motion
up to time $1$. We consider the following Schrödinger bridge problem

$\pi^{\star}=\operatorname*{arg\,min}\\{\operatorname{KL}(\pi|\pi^{0})\,:\;\pi\in\mathscr{P}(\mathbb{R}^{2d}),\
\pi_{0}=\nu_{0},\pi_{1}=\nu_{1}\\}.$ (442)

Before giving the analytic solution of the SB problem we consider the
following algebraic lemma.

######  Lemma .

Let $A\in\mathbb{R}^{d\times d}$ and

$M=\left(\begin{matrix}\mathbf{I}&A\\\
A^{\top}&\mathbf{I}\end{matrix}\right),\qquad
M^{S}=\left(\begin{matrix}\mathbf{I}&(A+A^{\top})/2\\\
(A+A^{\top})/2&\mathbf{I}\end{matrix}\right),$ (443)

such that $M$ is symmetric and positive semi-definite. Then
$\det(M)\leq\det(M^{S})$.

###### Proof.

Let $M^{\mathrm{up}}=M$ and
$M^{\mathrm{down}}=\left(\begin{matrix}\mathbf{I}&A^{\top}\\\
A&\mathbf{I}\end{matrix}\right)$. Since $M^{\mathrm{up}}$ is symmetric and
real-valued, $M^{\mathrm{up}}$ is diagonalizable. Let $x,y\in\mathbb{R}^{d}$
and $\theta\geq 0$ such that $M^{\mathrm{up}}X=\theta X$ with $X=(x,y)$. Let
$Y=(y,x)$. We have $M^{\mathrm{down}}Y=\theta Y$. Hence $M^{\mathrm{down}}$ is
symmetric, positive semi-definite and
$\det(M^{\mathrm{up}})=\det(M^{\mathrm{down}})$. Hence using that
$M\mapsto\log(\det(M))$ is concave on the space of symmetric positive semi-
definite matrices we get that
$\det(M^{\mathrm{up}})\leq\det((M^{\mathrm{up}}+M^{\mathrm{down}})/2)=\det(M^{S})$,
which concludes the proof. ∎

######  Proposition .

The solution to (442) exists and $\pi^{\star}$ is a Gaussian distribution with
mean $m\in\mathbb{R}^{2d}$ and covariance matrix
$\Sigma\in\mathbb{R}^{2d\times 2d}$ where

$\textstyle{m=(-a,a),\qquad\Sigma=\left(\begin{matrix}\mathbf{I}&\beta\mathbf{I}\\\
\beta\mathbf{I}&\mathbf{I}\end{matrix}\right),}$ (444)

where $\beta=(-1+\sqrt{5})/2$ and $\mathbf{I}$ is the $d$-dimensional identity
matrix.

###### Proof.

The fact that $\pi^{\star}$ exists and is Gaussian is similar to Section G.1.
$\pi^{\star}$ has mean $m$ since $\pi^{\star}_{i}=\nu_{i}$ for
$i\in\\{0,1\\}$. Similarly, we have that $\Sigma_{00}=\Sigma_{11}=\mathbf{I}$
since $\pi^{\star}_{i}=\nu_{i}$ for $i\in\\{0,1\\}$. We have that $\pi^{0}$
admits a density $p^{0}$ with respect to the Lebesgue measure such that for
any $x,y\in\mathbb{R}$ we have

$p^{0}(x,y)\propto\exp[-(1/2)\\{2\left\|x\right\|^{2}+\left\|y\right\|^{2}+2\langle
a,x\rangle-2\langle x,y\rangle+\left\|a\right\|^{2}\\}].$ (445)

Hence $\pi^{0}$ is a Gaussian distribution with mean $m^{0}$ and covariance
matrix $\Sigma^{0}$ where

$\textstyle{m^{0}=(-a,-a),\qquad\Sigma^{0}=\left(\begin{matrix}\mathbf{I}&\mathbf{I}\\\
\mathbf{I}&2\mathbf{I}\end{matrix}\right).}$ (446)

The Kullback–Leibler divergence between a Gaussian distribution $\pi$, with
mean $\tilde{m}$ and covariance matrix $\tilde{\Sigma}$, and $\pi^{0}$, with
mean $m^{0}$ and covariance $\Sigma^{0}$ is given by

$\textstyle{\operatorname{KL}(\pi|\pi^{0})=(1/2)\\{\log(\det(\Sigma^{0})/\det(\tilde{\Sigma}))-d+\operatorname{Tr}(\left(\Sigma^{0}\right)^{-1}\tilde{\Sigma})+(\tilde{m}-m^{0})^{\top}\left(\Sigma^{0}\right)^{-1}(\tilde{m}-m^{0})\\}.}$
(447)

Assume that $\tilde{m}=(-a,a)$ and
$\tilde{\Sigma}=\left(\begin{matrix}\mathbf{I}&S\\\
S^{\top}&\mathbf{I}\end{matrix}\right)$ with $S\in\mathbb{R}^{d\times d}$ such
that $\tilde{\Sigma}$ is positive semi-definite . Then we have

$\operatorname{KL}(\pi|\pi^{0})=(1/2)\\{-\log(\det(\tilde{\Sigma}))-2\operatorname{Tr}(S)+C\\},$
(448)

where $C\geq 0$ is a constant which does not depend on $\Sigma$. In what
follows, let
$\tilde{\Sigma^{\prime}}=\left(\begin{matrix}\mathbf{I}&(S+S^{\top})/2\\\
(S+S^{\top})/2&\mathbf{I}\end{matrix}\right)$ and denote $\pi$ the
distribution with mean $\tilde{m}$ and covariance matrix
$\tilde{\Sigma}^{\prime}$. Using Section G.2 we have

$\displaystyle\operatorname{KL}(\pi^{\prime}|\pi^{0})$
$\displaystyle=(1/2)\\{-\log(\det(\tilde{\Sigma}^{\prime}))-2\operatorname{Tr}(S)+C\\}$
(449)
$\displaystyle\leq(1/2)\\{-\log(\det(\tilde{\Sigma}))-2\operatorname{Tr}(S)+C\\}=\operatorname{KL}(\pi|\pi^{0}).$
(450)

Hence, we can assume that $S=S^{\top}$ and therefore (since $S$ is real-
valued), $S$ is diagonalizable. Let $\\{\lambda_{i}\\}_{i=1}^{d}$ the
eigenvalues of $S$. Using Schur complements (Petersen et al.,, 2008, Section
9.1.2) we have

$\textstyle{\det(\tilde{\Sigma})=\det(\mathbf{I}-S^{2})=\det(\mathbf{I}-S)\det(\mathbf{I}+S)=\prod_{i=1}^{d}(1-\lambda_{i}^{2}).}$
(451)

Therefore we have that for any $\lambda\in\left(0,1\right)$

$\textstyle{\operatorname{KL}(\pi|\pi^{0})=(1/2)\sum_{i=1}^{d}f(\beta_{i})+C,\qquad
f(\lambda)=-\log(1-\lambda^{2})-2\lambda.}$ (452)

Hence we get that $\Sigma_{0,1}=\beta\mathbf{I}$ with
$\beta=\operatorname*{arg\,min}_{I}f$, where
$I=\left(-1,0\right)\cup\left(0,1\right)$. We have that $f^{\prime}(\beta)=0$
if and only if $\beta=(-1+\sqrt{5})/2$ or $\beta=-(1+\sqrt{5})/2$. We conclude
the proof using that $\beta\in I$. ∎

##  Appendix H Continuous-time Schrödinger bridges

In this section, we prove Section 3.5 in Section H.1 and draw a link between
the potential approach to Schrödinger bridges and DSB in continuous time in
Section H.2.

###  H.1 Proof of Section 3.5

We recall the continuous Schrödinger problem is given by

$\textstyle{\Pi^{\star}=\operatorname*{arg\,min}\left\\{\operatorname{KL}(\Pi|\mathbb{P})\,:\;\Pi\in\mathscr{P}(\mathcal{C}),\
\Pi_{0}=p_{\textup{data}},\ \Pi_{T}=p_{\textup{prior}}\right\\},\quad
T=\sum_{k=0}^{N-1}\gamma_{k+1}.}$ (453)

In this section, we prove Section 3.5. We start with the following property
which can be found in (Léonard, 2014b, , Proposition 2.3, Proposition 2.10)
and establishes basic properties of dynamic continuous Schrödinger bridges.

######  Proposition .

The solution to (453) exists if and only if the solution to the static
Schrödinger bridge exists. In addition, if the solution exists and
$\mathbb{P}$ is Markov then the Schrödinger bridge is Markov.

We now turn to the proof of Section 3.5. First we highlight that
$(\Pi^{n})_{n\in\mathbb{N}}$ is well-defined since its static counterpart
$(\pi_{n})_{n\in\mathbb{N}}$ is well-defined using Section F.1.1. We only
prove that for any $n\in\mathbb{N}$, $(\Pi^{2n+1})^{R}$ is the path measure
associated with the process $(\mathbf{Y}_{t}^{2n+1})_{t\in\left[0,T\right]}$
such that $\mathbf{Y}_{0}^{2n+1}$ has distribution $p_{\textup{prior}}$ and
satisfies

$\textstyle{\mathrm{d}\mathbf{Y}_{t}^{2n+1}=b^{n}_{T-t}(\mathbf{X}_{t}^{2n+1})\mathrm{d}t+\sqrt{2}\mathrm{d}\mathbf{B}_{t}.}$
(454)

The proof for $\Pi^{2n+2}$ is similar. Let $n\in\mathbb{N}$ and assume that
$\Pi^{2n}$ is the path measure associated with the process
$(\mathbf{X}_{t}^{2n})_{t\in\left[0,T\right]}$ such that $\mathbf{X}_{0}^{2n}$
has distribution $p_{\textup{data}}$ and satisfies

$\textstyle{\mathrm{d}\mathbf{X}_{t}^{2n}=f^{n}_{t}(\mathbf{X}_{t}^{2n})\mathrm{d}t+\sqrt{2}\mathrm{d}\mathbf{B}_{t}.}$
(455)

We have that

$\textstyle{\Pi^{2n+1}=\operatorname*{arg\,min}\left\\{\operatorname{KL}(\Pi|\Pi^{2n})\,:\;\Pi\in\mathscr{P}(\mathcal{C}),\
\Pi_{T}=p_{\textup{prior}}\right\\}.}$ (456)

Let $\phi=\mathrm{proj}_{T}$ such that for any $\omega\in\mathcal{C}$,
$\mathrm{proj}_{T}(\omega)=\omega_{T}$. Using Section D.1 we get that for any
$\Pi\in\mathscr{P}(\mathcal{C})$ we have

$\textstyle{\operatorname{KL}(\Pi|\Pi^{2n})=\operatorname{KL}(\Pi_{T}|\Pi_{T}^{2n})+\int_{\mathbb{R}^{d}}\operatorname{KL}(\mathrm{K}(x,\cdot)|\mathrm{K}^{2n}(x,\cdot))\mathrm{d}\Pi_{T}(x),}$
(457)

where $\mathrm{K}$ and $\mathrm{K}^{2n}$ are the disintegrations of $\Pi$ and
$\Pi^{2n}$ with respect to $\phi$. Therefore, we get that
$\Pi^{2n+1}=p_{\textup{prior}}\mathrm{K}^{2n}$. Since
$\operatorname{KL}(\Pi^{2n}|\mathbb{Q})<+\infty$ and $\Pi^{2n}$ is Markov,
Using (Cattiaux et al.,, 2021, Theorem 4.9) we get that
$(\Pi^{2n})^{R}=\Pi_{T}\mathrm{K}^{2n}$ satisfies the martingale problem
associated with the diffusion

$\textstyle{\mathrm{d}\mathbf{Y}^{2n}_{t}=\left\\{-f^{n}_{T-t}(\mathbf{Y}^{2n}_{t})+2\nabla\log
p_{T-t}^{n}(\mathbf{Y}^{2n}_{t})\right\\}\mathrm{d}t+\sqrt{2}\mathrm{d}\mathbf{B}_{t}.}$
(458)

Since $\Pi^{2n+1}=p_{\textup{prior}}\mathrm{K}^{2n}$ we get that $\Pi^{2n+1}$
also satisfies the martingale problem associated with (458) and is Markov
which concludes the proof by recursion.

###  H.2 IPF in continuous time and potentials

First, we recall that the IPF $(\Pi^{n})_{n\in\mathbb{N}}$ with
$\Pi^{0}=\mathbb{P}$ associated with (8) and for any $n\in\mathbb{N}$

$\displaystyle\textstyle{\Pi^{2n+1}}$
$\displaystyle=\textstyle{\operatorname*{arg\,min}\left\\{\operatorname{KL}(\Pi|\Pi^{2n})\,:\;\Pi\in\mathscr{P}(\mathcal{C}),\
\Pi_{T}=p_{\textup{prior}}\right\\},}$ (459)
$\displaystyle\textstyle{\Pi^{2n+2}}$
$\displaystyle=\textstyle{\operatorname*{arg\,min}\left\\{\operatorname{KL}(\Pi|\Pi^{2n+1})\,:\;\Pi\in\mathscr{P}(\mathcal{C}),\
\Pi_{0}=p_{\textup{data}}\right\\}.}$ (460)

In this section, we draw a link between our time-reversal approach and the
potential approach in continuous time. More precisely, we explicit an identity
between the two in Section H.2.

######  Proposition .

Assume 1 and that there exist $\mathbb{M}\in\mathscr{P}(\mathcal{C})$,
$U\in\mathrm{C}^{1}(\mathbb{R}^{d},\mathbb{R})$, $C\geq 0$ such that for any
$n\in\mathbb{N}$, $x\in\mathbb{R}^{d}$,
$\operatorname{KL}(\Pi^{n}|\mathbb{M})<+\infty$, $\langle x,\nabla
U(x)\rangle\geq-C(1+\|x\|^{2})$ and $\mathbb{M}$ is associated with

$\textstyle{\mathrm{d}\mathbf{X}_{t}=-\nabla
U(\mathbf{X}_{t})\mathrm{d}t+\sqrt{2}\mathrm{d}\mathbf{B}_{t},}$ (461)

with $\mathbf{X}_{0}$ distributed according to the invariant distribution of
(33). For any $n\in\mathbb{N}$, let
$\\{\varphi_{t}^{n,\star},\varphi_{t}^{n,\circ}\\}_{t=0}^{T}$ such that for
any $t\in\left[0,T\right]$, $\varphi_{T}^{n,\star}:\
\mathbb{R}^{d}\to\mathbb{R}$, $\varphi_{0}^{n,\circ}:\
\mathbb{R}^{d}\to\mathbb{R}$, for any $x_{0},x_{T}\in\mathbb{R}^{d}$

$\varphi_{T}^{\star,n}(x_{T})=p_{\textup{prior}}(x_{T})/p_{T}^{n}(x_{T}),\qquad\varphi_{0}^{\circ,n}(x_{0})=p_{\textup{data}}(x_{0})/p_{0}^{n+1}(x_{0}),$
(462)

and for any $t\in\left(0,T\right)$ and $x_{t}\in\mathbb{R}^{d}$

$\textstyle{\varphi_{t}^{\star,n}(x_{t})=\int\varphi_{T}^{\star,n}(x_{T})p_{T|t}^{n}(x_{T}|x_{t})\mathrm{d}x_{T},\qquad\varphi_{t}^{\circ,n+1}(x)=\int\varphi_{0}^{\circ,n+1}(x_{0})q^{n}_{0|t}(x_{0}|x_{t})\mathrm{d}x_{0}.}$
(463)

We have for any $n\in\mathbb{N}$, $t\in\left[0,T\right]$ and
$x_{t}\in\mathbb{R}^{d}$

$q_{t}^{n}(x_{t})=p_{t}^{n}(x_{t})\varphi_{t}^{\star,n}(x_{t}),\qquad
p_{t}^{n+1}(x_{t})=q_{t}^{n}(x_{t})\varphi_{t}^{\circ,n}(x_{t}).$ (464)

In particular, for any $n\in\mathbb{N}$ we have

  1. (a)

$(\Pi^{2n+1})^{R}$ is associated with
$\mathrm{d}\mathbf{Y}_{t}^{2n+1}=b^{n}_{T-t}(\mathbf{Y}_{t}^{2n+1})\mathrm{d}t+\sqrt{2}\mathrm{d}\mathbf{B}_{t}$
with $\mathbf{Y}_{0}^{2n+1}\sim p_{\textup{prior}}$;

  2. (b)

$\Pi^{2n+2}$ is associated with
$\mathrm{d}\mathbf{X}_{t}^{2n+2}=f^{n+1}_{t}(\mathbf{X}_{t}^{2n+2})\mathrm{d}t+\sqrt{2}\mathrm{d}\mathbf{B}_{t}$
with $\mathbf{X}_{0}^{2n+2}\sim p_{\textup{data}}$;

with for any $x\in\mathbb{R}^{d}$ and $t\in\left(0,T\right)$

$\displaystyle\textstyle{f_{t}^{n}(x)=f(x)+2\sum_{k=1}^{n}\nabla\log\varphi_{t}^{\star,n}(x),\
b_{t}^{n}(x)=-f(x)+\nabla\log
p_{t}^{0}(x)+2\sum_{k=1}^{n}\nabla\log\varphi_{t}^{\circ,n}(x).}$ (465)

###### Proof.

We only prove that (464) holds. Then (465) is a direct consequence of (464)
and Section 3.5. Let $n\in\mathbb{N}$. Similarly to the proof of Section D.2,
there exists $\varphi_{T}^{\star,n}:\ \mathbb{R}^{d}\to\mathbb{R}_{+}$ such
that for any $\\{\omega_{t}\\}_{t=0}^{T}\in\mathcal{C}$ we have

$(\mathrm{d}\Pi^{2n+1}/\mathrm{d}\Pi^{2n})(\\{\omega_{t}\\}_{t=0}^{T})=\varphi_{T}^{\star,n}(\omega_{T}).$
(466)

Note that as in Section 3.5, that for any $s,t\in\left[0,T\right]$,
$\Pi^{2n+1}_{s,t}$ admits a positive density w.r.t the Lebesgue measure
denoted $q^{n}_{s,t}$ and $\Pi^{2n}_{s,t}$ admits a positive density w.r.t the
Lebesgue measure denoted $p^{n}_{s,t}$. Combining this result and (466), we
get that for any $t\in\left[0,T\right]$ and $x_{t},x_{T}\in\mathbb{R}^{d}$ we
have

$q_{t,T}^{n}(x_{t},x_{T})=p_{t,T}^{n}(x_{t},x_{T})\varphi_{T}^{\star,n}(x_{T}).$
(467)

We have that for any $t\in\left[0,T\right]$

$\textstyle{q_{t}(x_{t})=p_{t}^{n}(x_{t})\int\varphi_{T}^{\star,n}(x_{T})p_{T|t}^{n}(x_{T}|x_{t})\mathrm{d}x_{T}=p_{t}^{n}(x_{t})\varphi_{t}^{\star,n}(x_{t}).}$
(468)

The proof for that for any $n\in\mathbb{N}$, $t\in\left[0,T\right]$ and
$x_{t}\in\mathbb{R}^{d}$,
$p_{t}^{n+1}(x_{t})=q_{t}^{n}(x_{t})\varphi_{t}^{\circ,n}(x_{t})$, is similar.
∎

The link between the two formulations is explicit in (464). Then, (465) is a
straightforward consequence of (464) and should be compared with Section H.1.
Another proof of Section H.2 make use of a generalization of (464) to joint
densities and use the fact that for any $n\in\mathbb{N}$, $\Pi^{n+1}$ is a
Doob $h$-transform of $\Pi^{n}$ (see (Rogers and Williams,, 2000, Paragraph
39.1) for a definition). Note that this relationship between the potential and
the density of the half-bridge is not new. In particular, a similar version of
this equation can be found in Bernton et al., (2019). In Finlay et al.,
(2020), the authors establish a similar relationship in the case of the full
Schrödinger bridge.

###  H.3 Likelihood computation for Schrödinger bridges

We provide here details on the likelihood computation of generative models
obtained with Schrödinger bridges. Under the conditions of (Léonard,, 2011,
Theorem 4.12), we define $(\mathbf{X}_{t}^{\star})_{t\in\left[0,T\right]}$ the
diffusion associated with $\Pi^{\star}$, see (453) as well as its time
reversal, $(\mathbf{Y}_{t}^{\star})_{t\in\left[0,T\right]}$. There exist
$f^{\star},b^{\star}:\ \left[0,T\right]\times\mathbb{R}^{d}\to\mathbb{R}^{d}$
such that $(\mathbf{X}_{t}^{\star})_{t\in\left[0,T\right]}$ and
$(\mathbf{Y}_{t}^{\star})_{t\in\left[0,T\right]}$ are weak solutions to the
following SDEs

$\mathrm{d}\mathbf{X}_{t}^{\star}=f^{\star}_{t}(\mathbf{X}_{t}^{\star})\mathrm{d}t+\sqrt{2}\mathrm{d}\mathbf{B}_{t},\qquad\mathrm{d}\mathbf{Y}_{t}^{\star}=b^{\star}_{T-t}(\mathbf{Y}_{t}^{\star})\mathrm{d}t+\sqrt{2}\mathrm{d}\mathbf{B}_{t}.$
(469)

We assume that for any $t\in\left[0,T\right]$ there exists $p_{t}^{\star}:\
\mathbb{R}^{d}\to\mathbb{R}_{+}$ such that for any $x\in\mathbb{R}^{d}$,
$(\mathrm{d}\Pi^{\star}_{t}/\mathrm{d}\lambda)(x)=p_{t}^{\star}(x)$. In
addition, we assume that
$p^{\star}\in\mathrm{C}^{\infty}(\left[0,T\right]\times\mathbb{R}^{d},\mathbb{R}_{+})$.
In this case, we have that $\Pi^{\star}$ is also associated with the process
$(\tilde{\mathbf{X}}_{t}^{\star})_{t\in\left[0,T\right]}$ associated with the
ODE

$\mathrm{d}\tilde{\mathbf{X}}^{\star}_{t}=\\{f^{\star}_{t}(\tilde{\mathbf{X}}_{t}^{\star})-2\nabla\log
p_{t}^{\star}(\tilde{\mathbf{X}}_{t}^{\star})\\}\mathrm{d}t,$ (470)

and $\tilde{\mathbf{X}}_{T}^{\star}$ has distribution $p_{\textup{prior}}$;
see e.g. (Song et al.,, 2021, Section A). Since
$(\mathbf{Y}_{t}^{\star})_{t\in\left[0,T\right]}$ is the time-reversal of
$(\mathbf{X}_{t}^{\star})_{t\in\left[0,T\right]}$ we have that for any
$t\in\left[0,T\right]$ and $x\in\mathbb{R}^{d}$

$b^{\star}_{t}(x)=-f^{\star}_{t}(x)+2\nabla\log p_{t}^{\star}(x).$ (471)

Therefore, we get that
$(\tilde{\mathbf{X}}_{t}^{\star})_{t\in\left[0,T\right]}$ is associated with
the ODE

$\mathrm{d}\tilde{\mathbf{X}}^{\star}_{t}=-b^{\star}_{t}(\tilde{\mathbf{X}}_{t}^{\star})\mathrm{d}t.$
(472)

Using this result we can compute the log-likelihood of the model using the
instantaneous change of variable formula (Chen et al.,, 2018), see also (Song
et al.,, 2021, Appendix D.2)

$\textstyle{\log p_{\textup{data}}(\tilde{\mathbf{X}}_{0}^{\star})=\log
p_{\textup{prior}}(\tilde{\mathbf{X}}_{T}^{\star})-\int_{0}^{T}\mathrm{div}(b^{\star}_{t})(\tilde{\mathbf{X}}_{t}^{\star})\mathrm{d}t\;.}$
(473)

As in Song et al., (2021), we can use the Skilling–Hutchinson trace estimator
to compute the divergence operator (Skilling,, 1989; Hutchinson,, 1989). In
practice, we discretize the dynamics of
$(\tilde{\mathbf{X}}_{t}^{\star})_{t\in\left[0,T\right]}$ and use the network
$B_{\beta^{n}}$ obtained with the last iterate of Algorithm 1 and solve the
ODE backward in time, recalling that $\tilde{\mathbf{X}}_{T}^{\star}$ has
distribution $p_{\textup{prior}}$. Similarly, we can define

$\mathrm{d}\tilde{\mathbf{Y}}_{t}=\\{b^{\star}_{T-t}(\tilde{\mathbf{Y}}_{t}^{\star})-2\nabla\log
p_{T-t}^{\star}(\tilde{\mathbf{Y}}_{t}^{\star})\\}\mathrm{d}t,$ (474)

and $\mathbf{Y}_{0}^{\star}$ has distribution $p_{\textup{prior}}$. Similarly
to (472), we get that
$(\tilde{\mathbf{Y}}_{t}^{\star})_{t\in\left[0,T\right]}$ is associated with
the ODE

$\mathrm{d}\tilde{\mathbf{Y}}_{t}=-f^{\star}_{T-t}(\tilde{\mathbf{Y}}_{t}^{\star})\mathrm{d}t.$
(475)

Similarly to (476), we have

$\textstyle{\log p_{\textup{data}}(\tilde{\mathbf{Y}}_{T}^{\star})=\log
p_{\textup{prior}}(\tilde{\mathbf{Y}}_{0}^{\star})+\int_{0}^{T}\mathrm{div}(f^{\star}_{T-t})(\tilde{\mathbf{Y}}_{t}^{\star})\mathrm{d}t\;.}$
(476)

In practice, we discretize the dynamics of
$(\tilde{\mathbf{Y}}_{t}^{\star})_{t\in\left[0,T\right]}$ and use the network
$F_{\alpha^{n}}$ obtained with the last iterate of Algorithm 1 and solve the
ODE forward in time, recalling that $\tilde{\mathbf{Y}}_{0}^{\star}$ has
distribution $p_{\textup{prior}}$. Note that in this case, we solve the ODE
forward in time contrary to Durkan and Song, (2021).

##  Appendix I Training Techniques

In this section we present some practical guidelines for the implementation of
DSB, based on Algorithm 1. We emphasize that, contrarily to previous
approaches Song et al., (2021); Song and Ermon, (2020); Ho et al., (2020);
Dhariwal and Nichol, (2021), we do not weight the loss functions as we do not
notice any improvement. Let $I\subset\\{0,N-1\\}\times\\{1,M\\}$. We define
the generalized losses $\hat{\ell}_{n,I}^{b}$ and $\hat{\ell}_{n,I}^{f}$ given
by

$\displaystyle\textstyle{\hat{\ell}^{b}_{n,I}(\beta)=M^{-1}\sum_{(k,j)\in
I}\|B_{\beta}(k+1,X^{j}_{k+1})-(X^{j}_{k+1}+F^{n}_{k}(X^{j}_{k+1})-F^{n}_{k}(X^{j}_{k}))\|^{2}},$
(477)
$\displaystyle\textstyle{\hat{\ell}^{f}_{n+1,I}(\alpha)=M^{-1}\sum_{(k,j)\in
I}\|F_{\alpha}(k,X^{j}_{k})-(X^{j}_{k}+B^{n}_{k+1}(X^{j}_{k+1})-B^{n}_{k+1}(X^{j}_{k}))\|^{2}}.$
(478)

We first describe three techniques to compute these losses, then further
methods to improve performance.

######  Technique 1.

Simulated Trajectory

The losses (477) and (478) may be computed by simulating diffusion
trajectories as described in Algorithm 1. For each sample
$j\in\\{1,\ldots,M\\}$ the skeleton of points in the sampled trajectory,
$\\{X_{k}^{j}\\}_{k}$, will be correlated hence only a single uniformly
sampled time-step per sample is used to compute the loss per gradient step. In
addition, after the initial DSB iteration, simulating the diffusion trajectory
involves computationally heavy neural network operations per diffusion step.

######  Technique 2.

Closed Form Sampling

Since $f_{\alpha}^{0}(x)=-\alpha x$, with fixed $\alpha$, it is not necessary
to compute full trajectories for the first IPF iteration and one may sample
points along the trajectory in closed-form by sampling from a Gaussian
distribution with appropriate mean and covariance. This technique also
improves the computational speed of the first DSB iteration.

######  Technique 3.

Cached Trajectory

After the initial DSB iterations it is not possible perform closed form
sampling as per Technique 2. Simulating the full diffusion trajectory is both
wasteful and expensive as described in Technique 1. In order to obtain a
speed-up we consider a cached-version of Algorithm 1 given by Algorithm 3
which entails storing and then resampling diffusion trajectories. Resampled
trajectories are then used to compute losses (477) and (478). The cache may be
refreshed at a certain frequency by once again simulating the diffusion. One
may tune the cache-size and refresh frequency to available memory. This
modification allows for significant speed-up as the trajectories are not
simulated at each training iteration.

Algorithm 3 Cached Diffusion Schrödinger Bridge

1: for $n\in\\{0,\dots,L\\}$ do

2: while not converged do

3: Sample and store $\\{X^{j}_{k}\\}_{k,j=0}^{N,M}$ where $X^{j}_{0}\sim
p_{\textup{data}}$ and
$X^{j}_{k+1}=X^{j}_{k}+\gamma_{k+1}f_{\alpha^{n}}(k,X^{j}_{k})+\sqrt{2\gamma_{k+1}}Z^{j}_{k+1}$

4: while not refreshed do

5: Sample $I$ (uniform in $\\{0,N-1\\}\times\\{1,M\\}$)

6: Compute $\hat{\ell}^{b}_{n,I}(\beta^{n})$ using (477)

7: $\beta^{n}=\textrm{Gradient Step}(\hat{\ell}^{b}_{n,I}(\beta^{n}))$

8: end while

9: end while

10: while not converged do

11: Sample $\\{X^{j}_{k}\\}_{k,j=0}^{N,M}$, where $X^{j}_{N}\sim
p_{\textup{prior}}$, and
$X^{j}_{k}=X^{j}_{k+1}+\gamma_{k}b_{\beta^{n}}(k,X^{j}_{k})+\sqrt{2\gamma_{k+1}}Z^{j}_{k}$

12: while not refreshed do

13: Sample $I$ (uniform in $\\{0,N-1\\}\times\\{1,M\\}$)

14: Compute $\hat{\ell}^{f}_{n+1,I}(\alpha^{n+1})$ using (478)

15: $\alpha^{n+1}=\textrm{Gradient
Step}(\hat{\ell}^{f}_{n+1,I}(\alpha^{n+1}))$

16: end while

17: end while

18: end for

19: Output:  $(\alpha^{L+1},\beta^{L})$

######  Technique 4.

Tune Gaussian Prior mean/ variance

The convergence of the IPF is affected by the mean and covariance matrix of
the target Gaussian. In Section J.1 we investigate possible choices for these
values. In practice we recommend to choose the variance of the Gaussian prior
$p_{\textup{prior}}$ to be slightly larger than the one of the target dataset
and to choose the mean of $p_{\textup{prior}}$ to be equal to the one of the
target dataset. This remark is in accordance with (Song and Ermon,, 2020,
Technique 1).

######  Technique 5.

Network Refinement / Fine Tuning

Training large networks from scratch, per DSB iteration, is very expensive.
However, from (308)-(309),

$\displaystyle b_{k+1}^{n}(x)=\textstyle{b_{k+1}^{n-1}(x)+2\nabla\log
p_{k+1}^{n}(x)-2\nabla\log q_{k}^{n-1}(x),}$ (479) $\displaystyle
f_{k}^{n}(x)=\textstyle{f_{k}^{n-1}(x)+2\nabla\log q_{k}^{n-1}(x)-2\nabla\log
p_{k+1}^{n-1}(x).}$ (480)

One may therefore initialize networks at DBS iteration $n$ from $n-1$ in order
to reduce training time. In future work, we plan to investigate more
sophisticated warm-start approaches through meta-learning.

######  Technique 6.

Exponential Moving Average

Similar to (Song and Ermon,, 2020, Technique 5), we found taking the
exponential moving average of network parameters across training iterations,
with rate $0.999$, improved performance.

##  Appendix J  Additional Experimental Results and Details

We provide additional examples for the two-dimensional setting in Section J.1.
We then turn to higher dimensional generative modeling in Section J.2.
Finally, we detail our dataset interpolation experiments in Section J.3. Code
is available here: .

###  J.1 Two-dimensional experiments

In the case of two-dimensional distributions we use a simple architecture for
the networks $f_{\alpha}$ and $b_{\beta}$, see Figure 9. We use the
variational formulation Section E.2.2 because our network architecture does
not have a residual structure. To optimize our networks we use ADAM Kingma and
Ba, (2014) with momentum $0.9$ and learning rate $10^{-4}$.

OutputMLPBlock (2)ConcatenateMLPBlock (1a)MLPBlock
(1b)PositionalEncoding$x$$k$ Figure 9: Architecture of the networks used in
the two-dimensional setting. Each MLP Block is a Multilayer perceptron
network. The “PositionalEncoding” block applies the sine transform described
in Vaswani et al., (2017). MLPBlock (1a) has shape $(2,16,32)$, MLPBlock (1b)
has shape $(1,16,32)$ and MLPBlock has shape $(64,128,128,2)$. The total
number of parameters is 26498.

In all two-dimensional experiments we fix $\gamma_{k}=10^{-2}$ and use a batch
size of $512$. The mean and variance of $p_{\textup{prior}}$ are matched to
those of $p_{\textup{data}}$. The cache contains $10^{4}$ samples and is
refreshed every $10^{3}$ iterations. We train each DSB step for $10^{4}$
iterations. All two-dimensional experiments are run on Intel(R) Core(TM)
i7-10850H CPU @ 2.70GHz CPUs.

In Figure 10 we present additional two-dimensional experiments.

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

(i)

(j)

(k)

(l)

(m)

(n)

(o)

(p)

(q)

(r)

(s)

(t)

(u)

(v)

(w)

(x)

(y)

(z)

(aa)

(ab)

(ac)

(ad)

(ae)

(af)

Figure 10: The first row corresponds to iteration 1 of DSB, the second to