Résumé

We present an overview of our recent work on implementable solutions to the Schrödinger bridge problem and their potential application to optimal transport and various generalizations.

Optimal mass transport over bridges

Collection

application/pdf Optimal mass transport over bridges Yonxin Chen, Tryphon Georgiou, Michele Pavon

Média

Voir la vidéo

Métriques

148
12
1.75 Mo
 application/pdf
bitcache://c6a38e2fba7252179e1dc5e1af6e2e2642a3ad32

Licence

Creative Commons Attribution-ShareAlike 4.0 International

Sponsors

Organisateurs

logo_see.gif
logocampusparissaclay.png

Sponsors

entropy1-01.png
springer-logo.png
lncs_logo.png
Séminaire Léon Brillouin Logo
logothales.jpg
smai.png
logo_cnrs_2.jpg
gdr-isis.png
logo_gdr-mia.png
logo_x.jpeg
logo-lix.png
logorioniledefrance.jpg
isc-pif_logo.png
logo_telecom_paristech.png
csdcunitwinlogo.jpg
<resource  xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
                xmlns="http://datacite.org/schema/kernel-4"
                xsi:schemaLocation="http://datacite.org/schema/kernel-4 http://schema.datacite.org/meta/kernel-4/metadata.xsd">
        <identifier identifierType="DOI">10.23723/11784/14301</identifier><creators><creator><creatorName>Yonxin Chen</creatorName></creator><creator><creatorName>Tryphon Georgiou</creatorName></creator><creator><creatorName>Michele Pavon</creatorName></creator></creators><titles>
            <title>Optimal mass transport over bridges</title></titles>
        <publisher>SEE</publisher>
        <publicationYear>2015</publicationYear>
        <resourceType resourceTypeGeneral="Text">Text</resourceType><dates>
	    <date dateType="Created">Sun 8 Nov 2015</date>
	    <date dateType="Updated">Wed 31 Aug 2016</date>
            <date dateType="Submitted">Sun 16 Sep 2018</date>
	</dates>
        <alternateIdentifiers>
	    <alternateIdentifier alternateIdentifierType="bitstream">c6a38e2fba7252179e1dc5e1af6e2e2642a3ad32</alternateIdentifier>
	</alternateIdentifiers>
        <formats>
	    <format>application/pdf</format>
	</formats>
	<version>24691</version>
        <descriptions>
            <description descriptionType="Abstract">
We present an overview of our recent work on implementable solutions to the Schrödinger bridge problem and their potential application to optimal transport and various generalizations.

</description>
        </descriptions>
    </resource>
.

Optimal Mass Transport over Bridges Michele Pavon Department of Mathematics University of Padova, Italy GSI’15, Paris, October 29, 2015 Joint work with Yongxin Chen, Tryphon Georgiou, Department of Electrical and Computer Engineering, University of Minnesota A Venetian Schr¨odinger bridge Dynamic version of OMT “Fluid-dynamic” version of OMT (Benamou and Brenier (2000)): inf (ρ,v) Rn 1 0 1 2 v(x, t) 2ρ(x, t)dtdx, (1a) ∂ρ ∂t + · (vρ) = 0, (1b) ρ(x, 0) = ρ0(x), ρ(y, 1) = ρ1(y). (1c) Proposition 1 Let ρ∗(x, t) with t ∈ [0, 1] and x ∈ Rn, satisfy ∂ρ∗ ∂t + · ( ψρ∗) = 0, ρ∗(x, 0) = ρ0(x), where ψ is the (viscosity) solution of the Hamilton-Jacobi equation ∂ψ ∂t + 1 2 ψ 2 = 0 for some boundary condition ψ(x, 1) = ψ1(x). If ρ∗(x, 1) = ρ1(x), then the pair (ρ∗, v∗) with v∗(x, t) = ψ(x, t) is optimal for (1). Schr¨odinger’s Bridges • Cloud of N independent Brownian particles; • empirical distr. ρ0(x)dx and ρ1(y)dy at t = 0 and t = 1, resp. • ρ0 and ρ1 not compatible with transition mechanism ρ1(y) = 1 0 p(t0, x, t1, y)ρ0(x)dx, where p(s, y, t, x) = [2π(t − s)]−n 2 exp − |x − y|2 2(t − s) , s < t Particles have been transported in an unlikely way (N large). Schr¨odinger(1931): Of the many unlikely ways in which this could have happened, which one is the most likely? Schr¨odinger’s Bridges (cont’d) Schr¨odinger: solution (bridge from ρ0 to ρ1 over Brownian motion), has at each time a density ρ that factors as ρ(x, t) = ϕ(x, t) ˆϕ(x, t), where ϕ and ˆϕ solve Schr¨odinger’s system ϕ(x, t) = p(t, x, 1, y)ϕ(y, 1)dy, ϕ(x, 0) ˆϕ(x, 0) = ρ0(x) ˆϕ(x, t) = p(0, y, t, x) ˆϕ(y, 0)dy, ϕ(x, 1) ˆϕ(x, 1) = ρ1(x). F¨ollmer 1988: This is a problem of large deviations of the empirical distribution on path space connected through Sanov’s theorem to a maximum entropy problem. Existence and uniqueness for Schr¨odinger’s system: Fortet 1940, Beurling 1960, Jamison 1974/75, F¨ollmer 1988. Schr¨odinger’s Bridges as a control problem The maximum entropy formulation of the Schr¨odinger bridge prob- lem (SBP) with “prior” P is Minimize H(Q, P ) = EQ log dQ dP over D(ρ0, ρ1), where D be the family of distributions on Ω := C([0, 1], Rn) that are equivalent to stationary Wiener measure W = Wx dx. It can be turned, thanks to Girsanov’s theorem, into a stochastic control problem (Blaqui`ere, Dai Pra, M.P.-Wakolbinger, Filliger- Hongler-Streit,...) with fluid dynamic counterpart (P = W ) inf (ρ,v) Rn 1 0 1 2 v(x, t) 2ρ(x, t)dtdx, ∂ρ ∂t + · (vρ) − 2 ∆ρ = 0, ρ(x, 0) = ρ0(x), ρ(y, 1) = ρ1(y). Alternative time-symmetric fluid-dynamic for- mulation of SBP When prior is W stationary Wiener measure with variance inf (ρ,v) Rn 1 0 1 2 v(x, t) 2 + 8 log ρ(x, t) 2 ρ(x, t)dtdx, ∂ρ ∂t + · (vρ) = 0, ρ(0, x) = ρ0(x), ρ(1, y) = ρ1(y). With respect to Benamou and Brenier problem, extra term given by a Fisher information functional integrated over time. Answers at once question posed by Eric Carlen in 2006 investigating connections between OMT and Nelson’s stochastic mechanics. Schr¨odinger’s Bridges and OMT - Can we use SBP as a regular approximation of OMT? Yes, Mikami 2004, Mikami-Thieullen 2006,2008, L´eonard 2012. - Is this useful to compute solution to OMT? Problems: 1. Solution to control formulation of SBP not given in implementable form! 2 Control formulation of SBP only for non degenerate diffusions with control and noise entering through same channel! (excludes most engineering applications); 3 No steady-state theory; 4 No OMT problem with nontrivial prior! Gauss-Markov processes Problem 1. Find a control u minimizing J(u) := E 1 0 u(t) · u(t) dt , among those which achieve the transfer dXt = A(t)Xtdt + B(t)u(t)dt + B1(t)dWt, X0 ∼ N (0, Σ0), X1 ∼ N (0, Σ1). Engineering applications: Swarms of robots, shape bulk magne- tization distribution in NMR spectroscopy and imaging, industrial process control, ... If pair (A, B) is controllable (for constant A and B amounts to B, AB, ..., An−1B having full row rank), prob- lem always feasible (highly nontrivial, control may be “handicapped” with respect to the effect of noise). Gauss-Markov processes (cont’d) Problem 2. Find u = −Kx which minimizes Jpower(u) := E{u · u} and such that dx(t) = (A − BK)x(t)dt + B1dw(t) has ρ(x) = (2π)−n/2 det(Σ)−1/2 exp − 1 2 x Σ−1x as invariant probability density. Problem may not have a solution (not all values for Σ can be maintained by state feedback). Previous contributions: Beghi (1996,1997), Grigoriadis- Skelton (1997), Brockett (2007, 2012), Vladimirov-Petersen (2010, 2015) Gauss-Markov processes (cont’d) Sufficient conditions for optimality in terms of: - a system of two matrix Riccati equations (Lyapunov equations if B = B1) in the finite horizon case ˙Π = −A Π − ΠA + ΠBB Π ˙H = −A H − HA − HBB H + (Π + H) BB − B1B1 (Π + H) . Σ−1 0 = Π(0) + H(0) Σ−1 T = Π(T ) + H(T ). Gauss-Markov processes (cont’d) - in terms of algebraic conditions for the stationary case. rank AΣ + ΣA + B1B1 B B 0 = rank 0 B B 0 . Optimal controls may be computed via semidefinite programming in both cases. - Y. Chen, T.T. Georgiou and M. Pavon, Optimal steering of a linear stochastic system to a final probability distribution, Part I, Aug. 2014, arXiv:1408.2222v1, IEEE Trans. Aut. Control, to appear. - Y. Chen, T.T. Georgiou and M. Pavon, Optimal steering of a linear stochastic system to a final probability distribution, Part II, Oct. 2014, arXiv:1410.3447v1, IEEE Trans. Aut. Control, to appear. Cooling Two problems: • Efficient asymptotic steering of a system of stochastic oscillators to desired steady state ¯ρ; • Efficient steering of the system from initial condition ρ0 to ¯ρ at finite time t = 1. In both cases get solution for general system of nonlinear stochastic oscillators by extending Schr¨odinger bridges theory. - Y. Chen, T.T. Georgiou and M. Pavon, Fast cooling for a system of stochastic oscillators, arXiv:1411.1323v2, J. Math. Phys. Nov. 2015. OMT with “prior” inf (ρ,v) Rn 1 0 1 2 v(x, t) − vp(x, t) 2ρ(x, t)dtdx, (2a) ∂ρ ∂t + · (vρ) = 0, (2b) ρ(x, 0) = ρ0(x), ρ(y, 1) = ρ1(y). (2c) Proposition 2 Let ρ∗(x, t) with t ∈ [0, 1] and x ∈ Rn, satisfy ∂ρ∗ ∂t + · [(vp + ψ)ρ∗] = 0, ρ∗(x, 0) = ρ0(x), where ψ is the (viscosity) solution of the Hamilton-Jacobi equation ∂ψ ∂t + vp · ψ + 1 2 ψ 2 = 0 for boundary cond. ψ(x, 1) = ψ1(x). If ρ∗(x, 1) = ρ1(x), then the pair (ρ∗, v∗) with v∗(x, t) = vp(x, t) + ψ(x, t) is optimal for (2). OMT with “prior” (cont’d) Problem still in classical OMT framework inf π∈Π(µ,ν) Rn×Rn c(x, y)dπ(x, y), with c(x, y) = inf x∈Xxy 1 0 L(t, x(t), ˙x(t))dt, L(t, x, ˙x) = ˙x − vp(x, t) 2. Many results in OMT only for c(x, y) = c(x−y) strictly convex orig- inating from a Lagrangian L(t, x, ˙x) = c( ˙x). We are also interested in inf (ρ,u) Rn 1 0 1 2 u(x, t) 2ρ(x, t)dtdx, (3a) ∂ρ ∂t + · ((vp(x, t) + B(t)u(x, t))ρ) = 0, (3b) ρ(x, 0) = ρ0(x), ρ(y, 1) = ρ1(y). (3c) OMT and SBP Mikami (2004), L´eonard (2012) show, when prior is W , that as the diffusion coefficient tends to zero, OMT is Γ-limit of SBP. Hence infima converge and minimizers converge. In Gaussian case, we show directly convergence of solution to Hamilton-Jacobi-Bellman equation to solution of Hamilton-Jacobi equation also in case with prior. - Y. Chen, T.T. Georgiou and M. Pavon, On the relation between optimal transport and Schr¨odinger bridges: A stochastic control viewpoint, Dec. 2014, arXiv:1412.4430v1, J. Opt. Th. Appl., DOI: 10.1007/s10957-015-0803-z. - Y. Chen, T.T. Georgiou and M. Pavon, Optimal transport over a linear dynamical system, Feb. 2015, arXiv:1502.01265v1. OMT and SBP: Example Smoluchowski model for highly overdamped planar Brownian mo- tion in a force field is, in a strong sense, high-friction limit of full Ornstein-Uhlenbeck model in phase space dXt = − V (Xt)dt + √ dWt, − V (x) = Ax, A = −3 0 0 −3 , m0 = 5 5 , and Σ0 = 1 0 0 1 m1 = −5 −5 , and Σ1 = 1 0 0 1 Transparent tube represent the “3σ region” (x − mt)Σ−1 t (x − mt) ≤ 9. OMT and SBP: Example (cont’d) Interpolation based on Schr¨odinger bridge with = 9 Interpolation based on Schr¨odinger bridge with = 4 Interpolation based on Schr¨odinger bridge with = 0.01 Interpolation based on optimal transport with prior OMT and SBP in general How can we effectively compute the solution of the SBP in the general non Gaussian case? In T. T. Georgiou and M. Pavon, Positive contraction mappings for classical and quantum Schr¨odinger systems, May 2014, arXiv:1405.6650v2, J. Math. Phys., 56, 033301, March 2015. efficient iterative techniques to solve the Schr¨odinger system for Markov chains and Kraus maps of statistical quantum mechanics based on the Garrett Birkhoff (1957)-Bushell(1973) theorem. Application to general OMT - Y. Chen, T. Georgiou, and M. Pavon, Entropic and displacement interpolation: a computational approach using the Hilbert metric, June 2015, arXiv:1506.04255v1, submitted for publication. Applications to interpolation of 2D images to get 3D model. [t = 0] [t = 1] MRI slices at two different points [t = 0.2] [t = 0.4] [t = 0.6] [t = 0.8] Interpolation with = 0.01 THANK YOU FOR YOUR ATTENTION! References • T. T. Georgiou and M. Pavon, Positive contraction mappings for classical and quantum Schr¨odinger systems, arXiv:1405.6650v2, J. Math. Phys., 56, 033301, March 2015. • Y. Chen and T.T. Georgiou, Stochastic bridges of linear systems, preprint, arxiv: 1407.3421, IEEE Trans. Aut. Control, to appear. • Y. Chen, T.T. Georgiou and M. Pavon, Optimal steering of a linear stochastic system to a final probability distribution, Aug. 2014, arXiv:1408.2222v1, IEEE Trans. Aut. Control, to appear. • Y. Chen, T. Georgiou and M. Pavon, Optimal steering of inertial particles diffusing anisotropically with losses, arXiv 1410.1605v1, Oct. 7, 2014, Amer- ican Control Conf. 2015. • Y. Chen, T.T. Georgiou and M. Pavon, Optimal steering of a linear stochastic system to a final probability distribution, part II, Oct. 2014, arXiv:1410.3447v1, IEEE Trans. Aut. Control, to appear. • Y. Chen, T.T. Georgiou and M. Pavon, Fast cooling for a system of stochas- tic oscillators, Nov. 2014, arXiv:1411.1323v2, J. Math. Phys., Nov. 2015. • Y. Chen, T.T. Georgiou and M. Pavon, On the relation between optimal transport and Schr¨odinger bridges: A stochastic control viewpoint, Dec. 2014, arXiv:1412.4430v1, JOTA, to appear. • Y. Chen, T.T. Georgiou and M. Pavon, Optimal transport over a linear dynamical system, Feb. 2015, arXiv:1502.01265v1. References (cont’d) • Y. Chen, T.T. Georgiou and M. Pavon, Optimal mass transport over bridges, arXiv 1503.00215v1, Feb. 28, 2015, GSI’15 Conf.. • Y. Chen, T. Georgiou and M. Pavon, Steering state statistics with output feedback, arXiv 1504.00874v1, April 3, 2015, Proc. CDC 2015 (to appear). • Y. Chen, T.T. Georgiou and M. Pavon, Optimal control of the state statistics for a linear stochastic system, arXiv 1503.04885v1, March 17, 2015, Proc. CDC 2015 (to appear). • Y. Chen, T.T. Georgiou and M. Pavon, Entropic and displacement inter- polation: a computational approach using the Hilbert metric, June 2015, arXiv:1506.04255v1, submitted for publication. Markovian prior P with Nelson’s current velocity field vP (x, t) Minimize(ρ,v) t1 t0 RN 1 2σ2 v(x, t) − vP (x, t) 2 + 2 8 log ρ ρP (x, t) 2 ρ(x, t)dxdt, ∂ρ ∂t + · (vρ) = 0, ρt0 = ρ0, ρt1 = ρ1. Comparison with OMT with prior: There is here an extra term in the action functional which has the form of a relative Fisher information of ρt with respect to the prior one-time density ρP t (Dirichlet form) integrated over time. Decomposition of relative entropy H(Q, P ) = EQ log dQ dP = EQ log dµQ dµP (x(0), x(1)) + EQ   log dQ x(1) x(0) dP x(1) x(0) (x)    = log dµQ dµP dµQ + log dQ y x dP y x dQy xµQ(dx, dy). Thus, problem reduces to minimizing log dµQ dµP dµQ subject to the (linear) constraints µQ(dx × Rn) = ρ0(x)dx, µQ(Rn × dy) = ρ1(y)dy.