1.2PRJan 30, 2018
Optimal transport for Gaussian mixture modelsYongxin Chen, Tryphon T. Georgiou, Allen Tannenbaum
We present an optimal mass transport framework on the space of Gaussian mixture models, which are widely used in statistical inference. Our method leads to a natural way to compare, interpolate and average Gaussian mixture models. Basically, we study such models on a certain submanifold of probability densities with certain structure. Different aspects of this framework are discussed and several examples are presented to illustrate the results. This method represents our first attempt to study optimal transport problems for more general probability densities with structures.
6.6SYAug 10, 2014
Optimal steering of a linear stochastic system to a final probability distributionYongxin Chen, Tryphon Georgiou, Michele Pavon
We consider the problem to steer a linear dynamical system with full state observation from an initial gaussian distribution in state-space to a final one with minimum energy control. The system is stochastically driven through the control channels; an example for such a system is that of an inertial particle experiencing random "white noise" forcing. We show that a target probability distribution can always be achieved in finite time. The optimal control is given in state-feedback form and is computed explicitely by solving a pair of differential Lyapunov equations that are coupled through their boundary values. This result, given its attractive algorithmic nature, appears to have several potential applications such as to active control of nanomechanical systems and molecular cooling. The problem to steer a diffusion process between end-point marginals has a long history (Schrödinger bridges) and therefore, the present case of steering a linear stochastic system constitutes a Schrödinger bridge for possibly degenerate diffusions. Our results, however, provide the first implementable form of the optimal control for a general Gauss-Markov process. Illustrative examples of the optimal evolution and control for inertial particles and a stochastic oscillator are provided. A final result establishes directly the property of Schrödinger bridges as the most likely random evolution between given marginals to the present context of linear stochastic systems.
3.3OCFeb 4, 2015
Optimal transport over a linear dynamical systemYongxin Chen, Tryphon Georgiou, Michele Pavon
We consider the problem of steering an initial probability density for the state vector of a linear system to a final one, in finite time, using minimum energy control. In the case where the dynamics correspond to an integrator ($\dot x(t) = u(t)$) this amounts to a Monge-Kantorovich Optimal Mass Transport (OMT) problem. In general, we show that the problem can again be reduced to solving an OMT problem and that it has a unique solution. In parallel, we study the optimal steering of the state-density of a linear stochastic system with white noise disturbance; this is known to correspond to a Schrödinger bridge. As the white noise intensity tends to zero, the flow of densities converges to that of the deterministic dynamics and can serve as a way to compute the solution of its deterministic counterpart. The solution can be expressed in closed-form for Gaussian initial and final state densities in both cases.
1.2STAT-MECHMar 22, 2018
Stochastic control and non-equilibrium thermodynamics: fundamental limitsYongxin Chen, Tryphon Georgiou, Allen Tannenbaum
We consider damped stochastic systems in a controlled (time-varying) quadratic potential and study their transition between specified Gibbs-equilibria states in finite time. By the second law of thermodynamics, the minimum amount of work needed to transition from one equilibrium state to another is the difference between the Helmholtz free energy of the two states and can only be achieved by a reversible (infinitely slow) process. The minimal gap between the work needed in a finite-time transition and the work during a reversible one, turns out to equal the square of the optimal mass transport (Wasserstein-2) distance between the two end-point distributions times the inverse of the duration needed for the transition. This result, in fact, relates non-equilibrium optimal control strategies (protocols) to gradient flows of entropy functionals via and the Jordan-Kinderlehrer-Otto scheme. The purpose of this paper is to introduce ideas and results from the emerging field of stochastic thermodynamics in the setting of classical regulator theory, and to draw connections and derive such fundamental relations from a control perspective in a multivariable setting.
1.2SYMar 26, 2016
Robust transport over networksYongxin Chen, Tryphon T. Georgiou, Michele Pavon et al.
We consider transport over a strongly connected, directed graph. The scheduling amounts to selecting transition probabilities for a discrete-time Markov evolution which is designed to be consistent with certain initial and final marginals. The random evolution is selected to be closest to a prior measure on paths in the relative entropy sense, i.e., a Schroedinger bridge between the two marginals. This is an atypical stochastic control problem where the control consists in suitably modifying the transition mechanism. The prior can incorporate cost of traversing edges or allocate equal probability to all paths of equal length connecting any two given nodes, i.e., a uniform measure on paths. This latter choice relies on the so-called Ruelle-Bowen random walk and gives rise to a scheduling that tends to utilize all paths as uniformly as the topology allows. Thus, when the Ruelle-Bowen law is taken as prior, the transportation plan tends to lessen congestion and ensure a level of robustness. We show that the Ruelle-Bowen law is itself a Schroedinger bridge albeit with a prior that is not a probability measure. The paradigm of Schroedinger bridges as a mechanism for scheduling transport on networks can be adapted to graphs that are not strongly connected as well as to weighted graphs. The latter leads to transportation plans that effect a compromise between robustness and transportation cost.
6.3OCMay 5, 2012
The Separation Principle in Stochastic Control, ReduxTryphon T. Georgiou, Anders Lindquist
Over the last 50 years a steady stream of accounts have been written on the separation principle of stochastic control. Even in the context of the linear-quadratic regulator in continuous time with Gaussian white noise, subtle difficulties arise, unexpected by many, that are often overlooked. In this paper we propose a new framework for establishing the separation principle. This approach takes the viewpoint that stochastic systems are well-defined maps between sample paths rather than stochastic processes per se and allows us to extend the separation principle to systems driven by martingales with possible jumps. While the approach is more in line with "real-life" engineering thinking where signals travel around the feedback loop, it is unconventional from a probabilistic point of view in that control laws for which the feedback equations are satisfied almost surely, and not deterministically for every sample path, are excluded.
5.9SYJul 12, 2014
Stochastic bridges of linear systemsYongxin Chen, Tryphon Georgiou
We study a generalization of the Brownian bridge as a stochastic process that models the position and velocity of inertial particles between the two end-points of a time interval. The particles experience random acceleration and are assumed to have known states at the boundary. Thus, the movement of the particles can be modeled as an Ornstein-Uhlenbeck process conditioned on position and velocity measurements at the two end-points. It is shown that optimal stochastic control provides a stochastic differential equation (SDE) that generates such a bridge as a degenerate diffusion process. Generalizations to higher order linear diffusions are considered.
2.4OCJan 9, 2018
Measure-valued spline curves: an optimal transport viewpointYongxin Chen, Giovanni Conforti, Tryphon T. Georgiou
The aim of this article is to introduce and address the problem to smoothly interpolate (empirical) probability measures. To this end, we lift the concept of a spline curve from the setting of points in a Euclidean space that that of probability measures, using the framework of optimal transport.
1.2SYSep 15, 2012
Uncertainty Bounds for Spectral EstimationJohan Karlsson, Tryphon T. Georgiou
The purpose of this paper is to study metrics suitable for assessing uncertainty of power spectra when these are based on finite second-order statistics. The family of power spectra which is consistent with a given range of values for the estimated statistics represents the uncertainty set about the "true" power spectrum. Our aim is to quantify the size of this uncertainty set using suitable notions of distance, and in particular, to compute the diameter of the set since this represents an upper bound on the distance between any choice of a nominal element in the set and the "true" power spectrum. Since the uncertainty set may contain power spectra with lines and discontinuities, it is natural to quantify distances in the weak topology---the topology defined by continuity of moments. We provide examples of such weakly-continuous metrics and focus on particular metrics for which we can explicitly quantify spectral uncertainty. We then consider certain high resolution techniques which utilize filter-banks for pre-processing, and compute worst-case a priori uncertainty bounds solely on the basis of the filter dynamics. This allows the a priori tuning of the filter-banks for improved resolution over selected frequency bands.
2.6OCSep 29, 2017
Gradient Flows in Uncertainty Propagation and Filtering of Linear Gaussian SystemsAbhishek Halder, Tryphon T. Georgiou
The purpose of this work is mostly expository and aims to elucidate the Jordan-Kinderlehrer-Otto (JKO) scheme for uncertainty propagation, and a variant, the Laugesen-Mehta-Meyn-Raginsky (LMMR) scheme for filtering. We point out that these variational schemes can be understood as proximal operators in the space of density functions, realizing gradient flows. These schemes hold the promise of leading to efficient ways for solving the Fokker-Planck equation as well as the equations of non-linear filtering. Our aim in this paper is to develop in detail the underlying ideas in the setting of linear stochastic systems with Gaussian noise and recover known results.
1.2SYSep 14, 2014
Metrics for matrix-valued measures via test functionsLipeng Ning, Tryphon T. Georgiou
It is perhaps not widely recognized that certain common notions of distance between probability measures have an alternative dual interpretation which compares corresponding functionals against suitable families of test functions. This dual viewpoint extends in a straightforward manner to suggest metrics between matrix-valued measures. Our main interest has been in developing weakly-continuous metrics that are suitable for comparing matrix-valued power spectral density functions. To this end, and following the suggested recipe of utilizing suitable families of test functions, we develop a weakly-continuous metric that is analogous to the Wasserstein metric and applies to matrix-valued densities. We use a numerical example to compare this metric to certain standard alternatives including a different version of a matricial Wasserstein metric developed earlier.
1.2SYMay 12, 2016
Likelihood Analysis of Power Spectra and Generalized Moment ProblemsTryphon T. Georgiou, Anders Lindquist
We develop an approach to spectral estimation that has been advocated by Ferrante, Masiero and Pavon and, in the context of the scalar-valued covariance extension problem, by Enqvist and Karlsson. The aim is to determine the power spectrum that is consistent with given moments and minimizes the relative entropy between the probability law of the underlying Gaussian stochastic process to that of a prior. The approach is analogous to the framework of earlier work by Byrnes, Georgiou and Lindquist and can also be viewed as a generalization of the classical work by Burg and Jaynes on the maximum entropy method. In the present paper we present a new fast algorithm in the general case (i.e., for general Gaussian priors) and show that for priors with a specific structure the solution can be given in closed form.
2.5OCOct 17, 2011
Geometric methods for estimation of structured covariancesLipeng Ning, Xianhua Jiang, Tryphon Georgiou
We consider problems of estimation of structured covariance matrices, and in particular of matrices with a Toeplitz structure. We follow a geometric viewpoint that is based on some suitable notion of distance. To this end, we overview and compare several alternatives metrics and divergence measures. We advocate a specific one which represents the Wasserstein distance between the corresponding Gaussians distributions and show that it coincides with the so-called Bures/Hellinger distance between covariance matrices as well. Most importantly, besides the physically appealing interpretation, computation of the metric requires solving a linear matrix inequality (LMI). As a consequence, computations scale nicely for problems involving large covariance matrices, and linear prior constraints on the covariance structure are easy to handle. We compare this transportation/Bures/Hellinger metric with the maximum likelihood and the Burg methods as to their performance with regard to estimation of power spectra with spectral lines on a representative case study from the literature.
3.3OCMar 17, 2015
Optimal control of the state statistics for a linear stochastic systemYongxin Chen, Tryphon Georgiou, Michele Pavon
We consider a variant of the classical linear quadratic Gaussian regulator (LQG) in which penalties on the endpoint state are replaced by the specification of the terminal state distribution. The resulting theory considerably differs from LQG as well as from formulations that bound the probability of violating state constraints. We develop results for optimal state-feedback control in the two cases where i) steering of the state distribution is to take place over a finite window of time with minimum energy, and ii) the goal is to maintain the state at a stationary distribution over an infinite horizon with minimum power. For both problems the distribution of noise and state are Gaussian. In the first case, we show that provided the system is controllable, the state can be steered to any terminal Gaussian distribution over any specified finite time-interval. In the second case, we characterize explicitly the covariance of admissible stationary state distributions that can be maintained with constant state-feedback control. The conditions for optimality are expressed in terms of a system of dynamically coupled Riccati equations in the finite horizon case and in terms of algebraic conditions for the stationary case. In the case where the noise and control share identical input channels, the Riccati equations for finite-horizon steering become homogeneous and can be solved in closed form. The present paper is largely based on our recent work in arxiv.org/abs/1408.2222, arxiv.org/abs/1410.3447 and presents an overview of certain key results.
1.2SYJul 24, 2018
Dynamic relations in sampled processesTryphon T. Georgiou, Anders Lindquist
Linear dynamical relations that may exist in continuous-time, or at some natural sampling rate, are not directly discernable at reduced observational sampling rates. Indeed, at reduced rates, matricial spectral densities of vectorial time series have maximal rank and thereby cannot be used to ascertain potential dynamic relations between their entries. This hitherto undeclared source of inaccuracies appears to plague off-the-shelf identification techniques seeking remedy in hypothetical observational noise. In this paper we explain the exact relation between stochastic models at different sampling rates and show how to construct stochastic models at the finest time scale that data allows. We then point out that the correct number of dynamical dependences can only be ascertained by considering stochastic models at this finest time scale, which in general is faster than the observational sampling rate.
3.3OCMar 1, 2015
Optimal mass transport over bridgesYongxin Chen, Tryphon Georgiou, Michele Pavon
We present an overview of our recent work on implementable solutions to the Schroedinger bridge problem and their potential application to optimal transport and various generalizations.
2.3MNJul 15, 2023
Promotion/Inhibition Effects in Networks: A Model with Negative ProbabilitiesAnqi Dong, Tryphon T. Georgiou, Allen Tannenbaum
Biological networks often encapsulate promotion/inhibition as signed edge-weights of a graph. Nodes may correspond to genes assigned expression levels (mass) of respective proteins. The promotion/inhibition nature of co-expression between nodes is encoded in the sign of the corresponding entry of a sign-indefinite adjacency matrix, though the strength of such co-expression (i.e., the precise value of edge weights) cannot typically be directly measured. Herein we address the inverse problem to determine network edge-weights based on a sign-indefinite adjacency and expression levels at the nodes. While our motivation originates in gene networks, the framework applies to networks where promotion/inhibition dictates a stationary mass distribution at the nodes. In order to identify suitable edge-weights we adopt a framework of ``negative probabilities,'' advocated by P.\ Dirac and R.\ Feynman, and we set up a likelihood formalism to obtain values for the sought edge-weights. The proposed optimization problem can be solved via a generalization of the well-known Sinkhorn algorithm; in our setting the Sinkhorn-type ``diagonal scalings'' are multiplicative or inverse-multiplicative, depending on the sign of the respective entries in the adjacency matrix, with value computed as the positive root of a quadratic polynomial.
1.2SYDec 10, 2017
Steering the distribution of agents in mean-field and cooperative gamesYongxin Chen, Tryphon T. Georgiou, Michele Pavon
The purpose of this work is to pose and solve the problem to guide a collection of weakly interacting dynamical systems (agents, particles, etc.) to a specified terminal distribution. The framework is that of mean-field and of cooperative games. A terminal cost is used to accomplish the task; we establish that the map between terminal costs and terminal probability distributions is onto. Our approach relies on and extends the theory of optimal mass transport and its generalizations.
9.2SYApr 8
On the Isospectral Nature of Minimum-Shear Covariance ControlRalph Sabbagh, Asmaa Eldesoukey, Mahmoud Abdelgalil et al.
We revisit Brockett's attention in the context of bilinear gradient flow of an ensemble, and explore an alternative formalism that aims to reduce shear by minimizing the conditioning number of the dynamics; equivalently, we minimize the range of the eigenvalues of the dynamics. Remarkably, the evolution is isospectral, and this property is inherited by the coupled nonlinear dynamics of the control problem from a Lax isospectral flow.
5.7OCApr 26
Isospectral SteeringRalph Sabbagh, Tryphon T. Georgiou
We study the controllability of the differential Lyapunov equation under isospectral rotation of a linear gradient field. Specifically, control is effected by a symmetric time-varying gain-matrix constrained to have fixed eigenvalues; that is, by exclusively modulating the eigen-vectors of the state matrix and not its eigenvalues. Motivation for this problem stems from a certain type of control objectives (minimum shear/attention) aimed to reduce anisotropic deformation when ensembles are steered by a common law--optimality necessitates constancy of eigenvalues. In the paper we introduce and motivate this type of isospectral steering, and describe the reachable set of covariances for any specified terminal time and eigenvalues of the gain matrix. The theory we develop is intimately linked to multilinear algebra as well as to positive linear algebra and the Birkoff-von Neumann theorem for doubly stochastic matrices.
2.0IVSep 27, 2019Code
Fitting IVIM with Variable Projection and Simplicial OptimizationShreyas Fadnavis, Hamza Farooq, Maryam Afzali et al.
Fitting multi-exponential models to Diffusion MRI (dMRI) data has always been challenging due to various underlying complexities. In this work, we introduce a novel and robust fitting framework for the standard two-compartment IVIM microstructural model. This framework provides a significant improvement over the existing methods and helps estimate the associated diffusion and perfusion parameters of IVIM in an automatic manner. As a part of this work we provide capabilities to switch between more advanced global optimization methods such as simplicial homology (SH) and differential evolution (DE). Our experiments show that the results obtained from this simultaneous fitting procedure disentangle the model parameters in a reduced subspace. The proposed framework extends the seminal work originated in the MIX framework, with improved procedures for multi-stage fitting. This framework has been made available as an open-source Python implementation and disseminated to the community through the DIPY project.
1.0LGApr 14, 2019
Probabilistic Kernel Support Vector MachinesYongxin Chen, Tryphon T. Georgiou, Allen R. Tannenbaum
We propose a probabilistic enhancement of standard kernel Support Vector Machines for binary classification, in order to address the case when, along with given data sets, a description of uncertainty (e.g., error bounds) may be available on each datum. In the present paper, we specifically consider Gaussian distributions to model uncertainty. Thereby, our data consist of pairs $(x_i,Σ_i)$, $i\in\{1,\ldots,N\}$, along with an indicator $y_i\in\{-1,1\}$ to declare membership in one of two categories for each pair. These pairs may be viewed to represent the mean and covariance, respectively, of random vectors $ξ_i$ taking values in a suitable linear space (typically $\mathbb R^n$). Thus, our setting may also be viewed as a modification of Support Vector Machines to classify distributions, albeit, at present, only Gaussian ones. We outline the formalism that allows computing suitable classifiers via a natural modification of the standard "kernel trick." The main contribution of this work is to point out a suitable kernel function for applying Support Vector techniques to the setting of uncertain data for which a detailed uncertainty description is also available (herein, "Gaussian points").
1.2SYMay 16, 2019
Principles of lossless adjustable one-portsTryphon T. Georgiou, Faryar Jabbari, Malcolm C. Smith
This paper explores the possibility to construct two-terminal mechanical devices (one-ports) which are lossless and adjustable. To be lossless, the device must be passive (i.e. not requiring a power supply) and non-dissipative. To be adjustable, a parameter of the device should be freely variable in real time as a control input. For the simplest lossless one ports, the spring and inerter, the question is whether the stiffness and inertance may be varied freely in a lossless manner. We will show that the typical laws which have been proposed for adjustable springs and inerters are necessarily active and that it is not straightforward to modify them to achieve losslessness, or indeed passivity. By means of a physical construction using a lever with moveable fulcrum we will derive device laws for adjustable springs and inerters which satisfy a formal definition of losslessness. We further provide a construction method which does not require a power supply for physically realisable translational and rotary springs and inerters. The analogous questions for lossless adjustable electrical devices are examined.
1.2SYOct 10, 2018
Stability Theory of Stochastic Models in Opinion DynamicsZahra Askarzadeh, Rui Fu, Abhishek Halder et al.
We consider a certain class of nonlinear maps that preserve the probability simplex, i.e., stochastic maps, that are inspired by the DeGroot-Friedkin model of belief/opinion propagation over influence networks. The corresponding dynamical models describe the evolution of the probability distribution of interacting species. Such models where the probability transition mechanism depends nonlinearly on the current state are often referred to as {\em nonlinear Markov chains}. In this paper we develop stability results and study the behavior of representative opinion models. The stability certificates are based on the contractivity of the nonlinear evolution in the $\ell_1$-metric. We apply the theory to two types of opinion models where the adaptation of the transition probabilities to the current state is exponential and linear, respectively--both of these can display a wide range of behaviors. We discuss continuous-time and other generalizations.
1.2NAJun 26, 2017
An Efficient Algorithm for Matrix-Valued and Vector-Valued Optimal Mass TransportYongxin Chen, Eldad Haber, Kaoru Yamamoto et al.
We present an efficient algorithm for recent generalizations of optimal mass transport theory to matrix-valued and vector-valued densities. These generalizations lead to several applications including diffusion tensor imaging, color images processing, and multi-modality imaging. The algorithm is based on sequential quadratic programming (SQP). By approximating the Hessian of the cost and solving each iteration in an inexact manner, we are able to solve each iteration with relatively low cost while still maintaining a fast convergent rate. The core of the algorithm is solving a weighted Poisson equation, where different efficient preconditioners may be employed. We utilize incomplete Cholesky factorization, which yields an efficient and straightforward solver for our problem. Several illustrative examples are presented for both the matrix and vector-valued cases.
2.9OCMay 18, 2017
Vector-Valued Optimal Mass TransportYongxin Chen, Tryphon T. Georgiou, Allen Tannenbaum
We introduce the problem of transporting vector-valued distributions. In this, a salient feature is that mass may flow between vectorial entries as well as across space (discrete or continuous). The theory relies on a first step taken to define an appropriate notion of optimal transport on a graph. The corresponding distance between distributions is readily computable via convex optimization and provides a suitable generalization of Wasserstein-type metrics. Building on this, we define Wasserstein-type metrics on vector-valued distributions supported on continuous spaces as well as graphs. Motivation for developing vector-valued mass transport is provided by applications such as multi-color image processing, polarimetric radar, as well as network problems where resources may be vectorial.
5.1SYAug 11, 2016
Optimal steering of a linear stochastic system to a final probability distribution, Part IIIYongxin Chen, Tryphon T. Georgiou, Michele Pavon
The subject of this work has its roots in the so called Schroedginer Bridge Problem (SBP) which asks for the most likely distribution of Brownian particles in their passage between observed empirical marginal distributions at two distinct points in time. Renewed interest in this problem was sparked by a reformulation in the language of stochastic control. In earlier works, presented as Part I and Part II, we explored a generalization of the original SBP that amounts to optimal steering of linear stochastic dynamical systems between state-distributions, at two points in time, under full state feedback. In these works the cost was quadratic in the control input. The purpose of the present work is to detail the technical steps in extending the framework to the case where a quadratic cost in the state is also present. In the zero-noise limit, we obtain the solution of a (deterministic) mass transport problem with general quadratic cost.
3.3OCAug 18, 2015
Optimal estimation with missing observations via balanced time-symmetric stochastic modelsTryphon T. Georgiou, Anders Lindquist
We consider data fusion for the purpose of smoothing and interpolation based on observation records with missing data. Stochastic processes are generated by linear stochastic models. The paper begins by drawing a connection between time reversal in stochastic systems and all-pass extensions. A particular normalization (choice of basis) between the two time-directions allows the two to share the same orthonormalized state process and simplifies the mathematics of data fusion. In this framework we derive symmetric and balanced Mayne-Fraser-like formulas that apply simultaneously to smoothing and interpolation.
6.6MATH-PHJun 30, 2015
Fast cooling for a system of stochastic oscillatorsYongxin Chen, Tryphon Georgiou, Michele Pavon
We study feedback control of coupled nonlinear stochastic oscillators in a force field. We first consider the problem of asymptotically driving the system to a desired {\em steady state} corresponding to reduced thermal noise. Among the feedback controls achieving the desired asymptotic transfer, we find that the most efficient one {from an energy point of view} is characterized by {\em time-reversibility}. We also extend the theory of Schrödinger bridges to this model, thereby steering the system in {\em finite time} and with minimum effort to a target steady-state distribution. The system can then be maintained in this state through the optimal steady-state feedback control. The solution, in the finite-horizon case, involves a space-time harmonic function $φ$, and $-\logφ$ plays the role of an artificial, time-varying potential in which the desired evolution occurs. This framework appears extremely general and flexible and can be viewed as a considerable generalization of existing active control strategies such as macromolecular cooling. In the case of a quadratic potential, the results assume a form particularly attractive from the algorithmic viewpoint as the optimal control can be computed via deterministic matricial differential equations. An example involving inertial particles illustrates both transient and steady state optimal feedback control.
12.4OCJun 13, 2015
Entropic and displacement interpolation: a computational approach using the Hilbert metricYongxin Chen, Tryphon T. Georgiou, Michele Pavon
Monge-Kantorovich optimal mass transport (OMT) provides a blueprint for geometries in the space of positive densities -- it quantifies the cost of transporting a mass distribution into another. In particular, it provides natural options for interpolation of distributions (displacement interpolation) and for modeling flows. As such it has been the cornerstone of recent developments in physics, probability theory, image processing, time-series analysis, and several other fields. In spite of extensive work and theoretical developments, the computation of OMT for large scale problems has remained a challenging task. An alternative framework for interpolating distributions, rooted in statistical mechanics and large deviations, is that of Schroedinger bridges (entropic interpolation). This may be seen as a stochastic regularization of OMT and can be cast as the stochastic control problem of steering the probability density of the state-vector of a dynamical system between two marginals. In this approach, however, the actual computation of flows had hardly received any attention. In recent work on Schroedinger bridges for Markov chains and quantum evolutions, we noted that the solution can be efficiently obtained from the fixed-point of a map which is contractive in the Hilbert metric. Thus, the purpose of this paper is to show that a similar approach can be taken in the context of diffusion processes which i) leads to a new proof of a classical result on Schroedinger bridges and ii) provides an efficient computational scheme for both, Schroedinger bridges and OMT. We illustrate this new computational approach by obtaining interpolation of densities in representative examples such as interpolation of images.
3.3OCApr 3, 2015
Steering state statistics with output feedbackYongxin Chen, Tryphon T. Georgiou, Michele Pavon
Consider a linear stochastic system whose initial state is a random vector with a specified Gaussian distribution. Such a distribution may represent a collection of particles abiding by the specified system dynamics. In recent publications, we have shown that, provided the system is controllable, it is always possible to steer the state covariance to any specified terminal Gaussian distribution using state feedback. The purpose of the present work is to show that, in the case where only partial state observation is available, a necessary and sufficient condition for being able to steer the system to a specified terminal Gaussian distribution for the state vector is that the terminal state covariance be greater (in the positive-definite sense) than the error covariance of a corresponding Kalman filter.
6.6SYDec 15, 2014
On the relation between optimal transport and Schrödinger bridges: A stochastic control viewpointYongxin Chen, Tryphon Georgiou, Michele Pavon
We take a new look at the relation between the optimal transport problem and the Schrödinger bridge problem from the stochastic control perspective. We show that the connections are richer and deeper than described in existing literature. In particular: a) We give an elementary derivation of the Benamou-Brenier fluid dynamics version of the optimal transport problem; b) We provide a new fluid dynamics version of the Schrödinger bridge problem; c) We observe that the latter provides an important connection with optimal transport without zero noise limits; d) We propose and solve a fluid dynamic version of optimal transport with prior; e) We can then view optimal transport with prior as the zero noise limit of Schrödinger bridges when the prior is any Markovian evolution. In particular, we work out the Gaussian case. A numerical example of the latter convergence involving Brownian particles is also provided.
6.6SYOct 13, 2014
Optimal steering of a linear stochastic system to a final probability distribution, part IIYongxin Chen, Tryphon Georgiou, Michele Pavon
We consider the problem of minimum energy steering of a linear stochastic system to a final prescribed distribution over a finite horizon and to maintain a stationary distribution over an infinite horizon. We present sufficient conditions for optimality in terms of a system of dynamically coupled Riccati equations in the finite horizon case and algebraic in the stationary case. We then address the question of feasibility for both problems. For the finite-horizon case, provided the system is controllable, we prove that without any restriction on the directionality of the stochastic disturbance it is always possible to steer the state to any arbitrary Gaussian distribution over any specified finite time-interval. For the stationary infinite horizon case, it is not always possible to maintain the state at an arbitrary Gaussian distribution through constant state-feedback. It is shown that covariances of admissible stationary Gaussian distributions are characterized by a certain Lyapunov-like equation. We finally present an alternative to solving the system of coupled Riccati equations, by expressing the optimal controls in the form of solutions to (convex) semi-definite programs for both cases. We conclude with an example to steer the state covariance of the distribution of inertial particles to an admissible stationary Gaussian distribution over a finite interval, to be maintained at that stationary distribution thereafter by constant-gain state-feedback control.