Search

The purpose of the present work is to expand substantially the type of control and estimation problems that can be addressed following the paradigm of Schr\"odinger bridges, by incorporating termination (killing) of stochastic flows. Specifically, in the context of estimation, we seek the most likely evolution realizing measured spatio-temporal marginals of killed particles. In the context of control, we seek a suitable control action directing the killed process toward spatio-temporal probabilistic constraints. To this end, we derive a new Schr\"odinger system of coupled, in space and time, partial differential equations to construct the solution of the proposed problem. Further, we show that a Fortet-Sinkhorn type of algorithm is available to attain the associated bridge. A key feature of our framework is that the obtained bridge retains the Markovian structure in the prior process, and thereby, the corresponding controller takes the form of state feedback., Comment: 6 pages, 2 figures

Complex systems can be effectively modeled via graphs that encode networked interactions, where relations between entities or nodes are often quantified by signed edge weights, e.g., promotion/inhibition in gene regulatory networks, or encoding political of friendship differences in social networks. However, it is often the case that only an aggregate consequence of such edge weights that characterize relations may be directly observable, as in protein expression of in gene regulatory networks. Thus, learning edge weights poses a significant challenge that is further exacerbated for intricate and large-scale networks. In this article, we address a model problem to determine the strength of sign-indefinite relations that explain marginal distributions that constitute our data. To this end, we develop a paradigm akin to that of the Schr\"odinger bridge problem and an efficient Sinkhorn type algorithm (more properly, Schr\"odinger-Fortet-Sinkhorn algorithm) that allows fast convergence to parameters that minimize a relative entropy/likelihood criterion between the sought signed adjacency matrix and a prior. The formalism that we present represents a novel generalization of the earlier Schr\"odinger formalism in that marginal computations may incorporate weights that model directionality in underlying relations, and further, that it can be extended to high-order networks -- the Schr\"odinger-Fortet-Sinkhorn algorithm that we derive is applicable all the same and allows geometric convergence to a sought sign-indefinite adjacency matrix or tensor, for high-order networks. We demonstrate our framework with synthetic and real-world examples.

Schr\"odinger bridges have emerged as an enabling framework for unveiling the stochastic dynamics of systems based on marginal observations at different points in time. The terminology "bridge'' refers to a probability law that suitably interpolates such marginals. The theory plays a pivotal role in a variety of contemporary developments in machine learning, stochastic control, thermodynamics, and biology, to name a few, impacting disciplines such as single-cell genomics, meteorology, and robotics. In this work, we extend Schr\"odinger's paradigm of bridges to account for integral constraints along paths, in a way akin to Maximum Caliber - a Maximum Entropy principle applied in a dynamic context. The Maximum Caliber principle has proven useful to infer the dynamics of complex systems e.g., that model gene circuits and protein folding. We unify these two problems via a maximum likelihood formulation to reconcile stochastic dynamics with ensemble-path data. A variety of data types can be encompassed, ranging from distribution moments to average currents along paths. The framework enables inference of time-varying potential landscapes that drive the process. The resulting forces can be interpreted as the optimal control that drives the system in a way that abides by specified integral constraints. Analogous results are presented in a discrete-time, discrete-space setting and specialized to steady-state dynamics. We finish by illustrating the practical applicability of the framework through paradigmatic examples, such as that of bit erasure or protein folding. In doing so, we highlight the strengths of the proposed framework, namely, the generality of the theory, the ease of computation, and the ability to interpret results in terms of system dynamics. This is in contrast to Maximum-Caliber problems where the focus is typically on updating a probability law on paths., Comment: 17 pages, 3 figures

We consider overdamped Brownian particles with two degrees of freedom (DoF) that are confined in a time-varying quadratic potential and are in simultaneous contact with heat baths of different temperatures along the respective DoF. The anisotropy in thermal fluctuations can be used to extract work by suitably manipulating the confining potential. The question of what the maximal amount of work that can be extracted is has been raised in recent work, and has been computed under the simplifying assumption that the entropy of the distribution of particles (thermodynamic states) remains constant throughout a thermodynamic cycle. Indeed, it was shown that the maximal amount of work that can be extracted amounts to solving an isoperimetric problem, where the 2-Wasserstein length traversed by thermodynamic states quantifies dissipation that can be traded off against an area integral that quantifies work drawn out of the thermal anisotropy. Here, we remove the simplifying assumption on constancy of entropy. We show that the work drawn can be computed similarly to the case where the entropy is kept constant while the dissipation can be reduced by suitably tilting the thermodynamic cycle in a thermodynamic space with one additional dimension. Optimal cycles can be locally approximated by solutions to an isoperimetric problem in a tilted lower-dimensional subspace., Comment: 6 pages, 4 figures

Physical systems transition between states with finite speed that is limited by energetic costs. In this Letter, we derive bounds on transition times for general Langevin systems that admit a decomposition into reversible and irreversible dynamics, in terms of the Wasserstein distance between states and the energetic costs associated with respective reversible and irreversible currents. For illustration we discuss Brownian particles subject to arbitrary forcing., Comment: 7 pages, 1 figure

The problem of reconciling a prior probability law with data was introduced by E. Schr\"odinger in 1931/32. It represents an early formulation of a maximum likelihood problem. The specific formulation can also be seen as the control problem to modify the law of a diffusion process so as to match specifications on marginal distributions at given times. Thereby, in recent years, this so-called {\em Schr\"odinger Bridge problem} has been at the center of the development of uncertainty control. However, an unstudied facet of this program has been to address uncertainty in space and time, modeling the effect of tasks being completed, instead of imposing specifications at fixed times. The present work is a first study to extend Schr\"odinger's paradigm on such an issue. It is developed in the context of Markov chains and random walks on graphs. Specifically, we study the case where one marginal distribution represents the initial state occupation of a Markov chain, while others represent first-arrival time distributions at absorbing states signifying completion of tasks. We establish that when the prior is Markov, a Markov policy is once again optimal with respect to a likelihood cost that follows Schr\"odinger's dictum., Comment: 11 pages, 3 figures

In this paper we extend recent developments in computational optimal transport to the setting of Riemannian manifolds. In particular, we show how to learn optimal transport maps from samples that relate probability distributions defined on manifolds. Specializing these maps for sampling conditional probability distributions provides an ensemble approach for solving nonlinear filtering problems defined on such geometries. The proposed computational methodology is illustrated with examples of transport and nonlinear filtering on Lie groups, including the circle $S^1$, the special Euclidean group $SE(2)$, and the special orthogonal group $SO(3)$., Comment: 6 pages, 7 figures

The purpose of this work is to develop a framework to calibrate signed datasets so as to be consistent with specified marginals by suitably extending the Schr\"odinger-Fortet-Sinkhorn paradigm. Specifically, we seek to revise sign-indefinite multi-dimensional arrays in a way that the updated values agree with specified marginals. Our approach follows the rationale in Schr\"odinger's problem, aimed at updating a "prior" probability measure to agree with marginal distributions. The celebrated Sinkhorn's algorithm (established earlier by R.\ Fortet) that solves Schr\"odinger's problem found early applications in calibrating contingency tables in statistics and, more recently, multi-marginal problems in machine learning and optimal transport. Herein, we postulate a sign-indefinite prior in the form of a multi-dimensional array, and propose an optimization problem to suitably update this prior to ensure consistency with given marginals. The resulting algorithm generalizes the Sinkhorn algorithm in that it amounts to iterative scaling of the entries of the array along different coordinate directions. The scaling is multiplicative but also, in contrast to Sinkhorn, inverse-multiplicative depending on the sign of the entries. Our algorithm reduces to the classical Sinkhorn algorithm when the entries of the prior are positive., Comment: 11 pages, 4 figures

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., Comment: 6 pages

A paradigm put forth by E. Schr\"odinger in 1931/32, known as Schr\"odinger bridges, represents a formalism to pose and solve control and estimation problems seeking a perturbation from an initial control schedule (in the case of control), or from a prior probability law (in the case of estimation), sufficient to reconcile data in the form of marginal distributions and minimal in the sense of relative entropy to the prior. In the same spirit, we consider traffic-flow and apply a Schr\"odinger-type dictum, to perturb minimally with respect to a suitable relative entropy functional a prior schedule/law so as to reconcile the traffic flow with scarce aggregate distributions on families of indistinguishable individuals. Specifically, we consider the problem to regulate/estimate multi-commodity network flow rates based only on empirical distributions of commodities being transported (e.g., types of vehicles through a network, in motion) at two given times. Thus, building on Schr\"odinger's large deviation rationale, we develop a method to identify {\em the most likely flow rates (traffic flow)}, given prior information and aggregate observations. Our method further extends the Schr\"odinger bridge formalism to the multi-commodity setting, allowing commodities to exit or enter the flow field as well (e.g., vehicles to enter and stop and park) at any time. The behavior of entering or exiting the flow field, by commodities or vehicles, is modeled by a Markov chains with killing and creation states. Our method is illustrated with a numerical experiment., Comment: 12 pages, 5 figures

In finite-dimensions, minimal surfaces that fill in the space delineated by closed curves and have minimal area arose naturally in classical physics in several contexts. No such concept seems readily available in infinite dimensions. The present work is motivated by the need for precisely such a concept that would allow natural coordinates for a surface with a boundary of a closed curve in the Wasserstein space of probability distributions (space of distributions with finite second moments). The need for such a concept arose recently in stochastic thermodynamics, where the Wasserstein length in the space of thermodynamic states quantifies dissipation while area integrals (albeit, presented in a special finite-dimensional parameter setting) relate to useful work being extracted. Our goal in this work is to introduce the concept of a minimal surface and explore options for a suitable construction. To this end, we introduce the basic mathematical problem and develop two alternative formulations. Specifically, we cast the problem as a two-parameter Benamou-Breiner type minimization problem and derive a minimal surface equation in the form of a set of two-parameter partial differential equations. Several explicit solutions for minimal surface equations in Wasserstein spaces are presented. These are cast in terms of covariance matrices in Gaussian distributions.

Gradients in temperature and particle concentration fuel many processes in the physical and biological world. In the present work we study a thermodynamic engine powered by anisotropic thermal excitation (that may be due to e.g., a temperature gradient), and draw parallels with the well-known principle of impedance matching in circuit theory, where for maximal power transfer, the load voltage needs to be half of that of the supplying power source. We maximize power output of the thermodynamic engine at steady-state and show that the optimal reactive force is precise half of that supplied by the anisotropy., Comment: 6 pages, 3 figures

Anisotropy in temperature, chemical potential, or ion concentration, provides the fuel that feeds dynamical processes that sustain life. At the same time, anisotropy is a root cause of incurred losses manifested as entropy production. In this work we consider a rudimentary model of an overdamped stochastic thermodynamic system in an anisotropic temperature heat bath, and study minimum entropy production when driving the system between thermodynamic states in finite time. While entropy production in isotropic temperature environments can be expressed in terms of the length (in the Wasserstein-2 metric) traversed by the thermodynamic state of the system, anisotropy complicates substantially the mechanism of entropy production since, besides dissipation, seepage of energy between ambient anisotropic heat sources by way of the system dynamics is often a major contributing factor. A key result of the paper is to show that in the presence of anisotropy, minimization of entropy production can once again be expressed via a modified Optimal Mass Transport (OMT) problem. However, in contrast to the isotropic situation that leads to a classical OMT problem and a Wasserstein length, entropy production may not be identically zero when the thermodynamic state remains unchanged (unless one has control over non-conservative forces); this is due to the fact that maintaining a Non-Equilibrium Steady-State (NESS) incurs an intrinsic entropic cost that can be traced back to a seepage of heat between heat baths. As alluded to, NESSs represent hallmarks of life, since living matter by necessity operates far from equilibrium. Therefore, the question studied herein, to characterize minimal entropy production in anisotropic environments, appears of central importance in biological processes and on how such processes may have evolved to optimize for available usage of resources., Comment: 16 pages, 4 figures

We consider the problem to transport resources/mass while abiding by constraints on the flow through constrictions along their path between specified terminal distributions. Constrictions, conceptualized as toll stations at specified points, limit the flow rate across. We quantify flow-rate constraints via a bound on a sought probability density of the times that mass-elements cross toll stations and cast the transportation scheduling in a Kantorovich-type of formalism. Recent work by our team focused on the existence of Monge maps for similarly constrained transport minimizing average kinetic energy. The present formulation in this paper, besides being substantially more general, is cast as a (generalized) multi-marginal transport problem - a problem of considerable interest in modern-day machine learning literature and motivated extensive computational analyses. An enabling feature of our formalism is the representation of an average quadratic cost on the speed of transport as a convex constraint that involves crossing times., Comment: 8 pages, 6 figures

Anisotropy of temperature fields, chemical potentials and ion concentration gradients provide the fuel that feeds dynamical processes that sustain life. Dynamical flows in respective environments incur losses manifested as entropy production. In this work we consider a rudimentary model of an overdamped stochastic thermodynamic system in an anisotropic temperature heat bath, and analyze the problem to minimize entropy production while driving the system between thermodynamic states in finite time. It is noted that entropy production in a fully isotropic temperature field, can be expressed as the Wasserstein-2 length of the path traversed by the thermodynamic state of the system. In the presence of an anisotropic temperature field, the mechanism of entropy production is substantially more complicated as, besides dissipation, it entails seepage of energy between the ambient heat sources by way of the system dynamics. We show that, in this case, the entropy production can be expressed as the solution of a suitably constrained and generalized Optimal Mass Transport (OMT) problem. In contrast to the situation in standard OMT, entropy production may not be identically zero, even when the thermodynamic state remains unchanged. Physically, this is due to the fact that maintaining a Non-Equilibrium Steady State (NESS), incurs an intrinsic entropic cost. As already noted, NESSs are the hallmark of life and living systems by necessity operate away from equilibrium. Thus our problem of minimizing entropy production appears of central importance in understanding biological processes, such as molecular motors and motor proteins, and on how such processes may have evolved to optimize for available usage of resources., Comment: 6 pages

We address the problem of optimal transport with a quadratic cost functional and a constraint on the flux through a constriction along the path. The constriction, conceptually represented by a toll station, limits the flow rate across. We provide a precise formulation which, in addition, is amenable to generalization in higher dimensions. We work out in detail the case of transport in one dimension by proving existence and uniqueness of solution. Under suitable regularity assumptions we give an explicit construction of the transport plan. Generalization of flux constraints to higher dimensions and possible extensions of the theory are discussed., Comment: 19 pages, 5 figures

A typical model for a gyrating engine consists of an inertial wheel powered by an energy source that generates an angle-dependent torque. Examples of such engines include a pendulum with an externally applied torque, Stirling engines, and the Brownian gyrating engine. Variations in the torque are averaged out by the inertia of the system to produce limit cycle oscillations. While torque generating mechanisms are also ubiquitous in the biological world, where they typically feed on chemical gradients, inertia is not a property that one naturally associates with such processes. In the present work, seeking ways to dispense of the need for inertial effects, we study an inertia-less concept where the combined effect of coupled torque-producing components averages out variations in the ambient potential and helps overcome dissipative forces to allow sustained operation for vanishingly small inertia. We exemplify this inertia-less concept through analysis of two of the aforementioned engines, the Stirling engine and the Brownian gyrating engine. An analogous principle may be sought in biomolecular processes as well as in modern-day technological engines, where for the latter, the coupled torque-producing components reduce vibrations that stem from the variability of the generated torque., Comment: 9 pages, 7 figures

In the present paper, we study the power output and efficiency of overdamped stochastic thermodynamic engines that are in contact with a heat bath having a temperature that varies periodically with time. This is in contrast to most of the existing literature that considers the Carnot paradigm of alternating contact with heat baths having different fixed temperatures, hot and cold. Specifically, we consider a periodic and bounded but otherwise arbitrary temperature profile and derive explicit bounds on the power and efficiency achievable by a suitable controlling potential that couples the thermodynamic engine to the external world. Standing assumptions in our analysis are bounds on the norm of the gradient of effective potentials -- in the absence of any such constraint, the physically questionable conclusion of arbitrarily large power can be drawn., Comment: 14 pages

In contrast to the classical concept of a Carnot engine that alternates contact between heat baths of different temperatures, naturally occurring processes usually harvest energy from anisotropy, being exposed simultaneously to chemical and thermal fluctuations of different intensities. In these cases, the enabling mechanism responsible for transduction of energy is typically the presence of a non-equilibrium steady state (NESS). A suitable stochastic model for such a phenomenon is the Brownian gyrator -- a two-degree of freedom stochastically driven system that exchanges energy and heat with the environment. In the context of such a model we present, from a stochastic control perspective, a geometric view of the energy harvesting mechanism that entails a forced periodic trajectory of the system state on the thermodynamic manifold. Dissipation and work output are expressed accordingly as path integrals of a controlled process, and fundamental limitations on power and efficiency are expressed in geometric terms via a relationship to an isoperimetric problem. The theory is presented for high-order systems far from equilibrium and beyond the linear response regime., Comment: 6 pages, 2 figures. arXiv admin note: text overlap with arXiv:2108.00334

The purpose of this work is to present the concept of an autonomous Stirling-like engine powered by anisotropy of thermodynamic fluctuations. Specifically, simultaneous contact of a thermodynamic system with two heat baths along coupled degrees of freedom generates torque and circulatory currents -- an arrangement referred to as a Brownian gyrator. The embodiment that constitutes the engine includes an inertial wheel to sustain rotary motion and average out the generated fluctuating torque, ultimately delivering power to an external load. We detail an electrical model for such an engine that consists of two resistors in different temperatures and three reactive elements in the form of variable capacitors. The resistors generate Johnson-Nyquist current fluctuations that power the engine, while the capacitors generate driving forces via a coupling of their dielectric material with the inertial wheel. A proof-of-concept is established via stability analysis to ensure the existence of a stable periodic orbit generating sustained power output. We conclude by drawing a connection to the dynamics of a damped pendulum with constant torque and to those of a macroscopic Stirling engine. The sought insights aim at nano-engines and biological processes that are similarly powered by anisotropy in temperature and chemical potentials., Comment: 6 pages, 6 figures, 1 table

Stochastic flows of an advective-diffusive nature are ubiquitous in physical sciences. Of particular interest is the problem to reconcile observed marginal distributions with a given prior posed by E. Schrodinger in 1932/32 and known as the Schrodinger Bridge Problem (SBP). Due to its fundamental significance, interest in SBP has in recent years enticed a broad spectrum of disciplines. Yet, while the mathematics and applications of SBP have been developing at a considerable pace, accounting for marginals of unequal mass has received scant attention; the problem to interpolate between unbalanced marginals has been approached by introducing source/sink terms in an Adhoc manner. Nevertheless, losses are inherent in many physical processes and, thereby, models that account for lossy transport may also need to be reconciled with observed marginals following Schrodinger's dictum; that is, to adjust the probability of trajectories of particles, including those that do not make it to the terminal observation point, so that the updated law represents the most likely way that particles may have been transported, or vanished, at some intermediate point. Thus, the purpose of this work is to develop such a natural generalization of the SBP for stochastic evolution with losses, whereupon particles are "killed" according to a probabilistic law. Through a suitable embedding, we turn the problem into an SBP for stochastic processes that combine diffusive and jump characteristics. Then, following a large-deviations formalism, given a prior law that allows for losses, we ask for the most probable evolution of particles along with the most likely killing rate as the particles transition between the specified marginals. Our approach differs sharply from previous work involving a Feynman-Kac multiplicative reweighing of the reference measure: The latter, as we argue, is far from Schrodinger's quest., Comment: 22 pages, 4 figures

We consider a rudimentary model for a heat engine, known as the Brownian gyrator, that consists of an overdamped system with two degrees of freedom in an anisotropic temperature field. Whereas the hallmark of the gyrator is a nonequilibrium steady-state curl-carrying probability current that can generate torque, we explore the coupling of this natural gyrating motion with a periodic actuation potential for the purpose of extracting work. We show that path-lengths traversed in the manifold of thermodynamic states, measured in a suitable Riemannian metric, represent dissipative losses, while area integrals of a work-density quantify work being extracted. Thus, the maximal amount of work that can be extracted relates to an isoperimetric problem, trading off area against length of an encircling path. We derive an isoperimetric inequality that provides a universal bound on the efficiency of all cyclic operating protocols, and a bound on how fast a closed path can be traversed before it becomes impossible to extract positive work. The analysis presented provides guiding principles for building autonomous engines that extract work from anistropic fluctuations., Comment: 5 pages 5 figures

We formulate and solve a regression problem with time-stamped distributional data. Distributions are considered as points in the Wasserstein space of probability measures, metrized by the 2-Wasserstein metric, and may represent images, power spectra, point clouds of particles, and so on. The regression seeks a curve in the Wasserstein space that passes closest to the dataset. Our regression problem allows utilizing general curves in a Euclidean setting (linear, quadratic, sinusoidal, and so on), lifted to corresponding measure-valued curves in the Wasserstein space. It can be cast as a multi-marginal optimal transport problem that allows efficient computation. Illustrative academic examples are presented.

We revisit the setting and the assumptions that underlie the methodology of Dynamic Mode Decomposition (DMD) in order to highlight caveats as well as potential measures of when the applicability is warranted.

The common saying, that information is power, takes a rigorous form in stochastic thermodynamics, where a quantitative equivalence between the two helps explain the paradox of Maxwell's demon in its ability to reduce entropy. In the present paper, we build on earlier work on the interplay between the relative cost and benefits of information in producing work in cyclic operation of thermodynamic engines (by Sandberg etal. 2014). Specifically, we study the general case of overdamped particles in a time-varying potential (control action) in feedback that utilizes continuous measurements (nonlinear filtering) of a thermodynamic ensemble, to produce suitable adaptations of the second law of thermodynamics that involve information.

We derive novel results on the ergodic theory of irreducible, aperiodic Markov chains. We show how to optimally steer the network flow to a stationary distribution over a finite or infinite time horizon. Optimality is with respect to an entropic distance between distributions on feasible paths. When the prior is reversible, it shown that solutions to this discrete time and space steering problem are reversible as well. A notion of temperature is defined for Boltzmann distributions on networks, and problems analogous to cooling (in this case, for evolutions in discrete space and time) are discussed., Comment: 7 pages

We study thermodynamic processes in contact with a heat bath that may have an arbitrary time-varying periodic temperature profile. Within the framework of stochastic thermodynamics, and for models of thermo-dynamic engines in the idealized case of underdamped particles in the low-friction regime, we derive explicit bounds as well as optimal control protocols that draw maximum power and achieve maximum efficiency at any specified level of power.

The context of the present paper is stochastic thermodynamics - an approach to nonequilibrium thermodynamics rooted within the broader framework of stochastic control. In contrast to the classical paradigm of Carnot engines, we herein propose to consider thermodynamic processes with periodic continuously varying temperature of a heat bath and study questions of maximal power and efficiency for two idealized cases, overdamped (first-order) and underdamped (second-order) stochastic models. We highlight properties of optimal periodic control, derive and numerically validate approximate formulae for the optimal performance (power and efficiency)., Comment: 9 pages, 2 figures. Conference

This manuscript introduces a regression-type formulation for approximating the Perron-Frobenius Operator by relying on distributional snapshots of data. These snapshots may represent densities of particles. The Wasserstein metric is leveraged to define a suitable functional optimization in the space of distributions. The formulation allows seeking suitable dynamics so as to interpolate the distributional flow in function space. A first-order necessary condition for optimality is derived and utilized to construct a gradient flow approximating algorithm. The framework is exemplied with numerical simulations., Comment: 11 pages

This paper is concerned with optimality and stability analysis of a family of ensemble Kalman filter (EnKF) algorithms. EnKF is commonly used as an alternative to the Kalman filter for high-dimensional problems, where storing the covariance matrix is computationally expensive. The algorithm consists of an ensemble of interacting particles driven by a feedback control law. The control law is designed such that, in the linear Gaussian setting and asymptotic limit of infinitely many particles, the mean and covariance of the particles follow the exact mean and covariance of the Kalman filter. The problem of finding a control law that is exact does not have a unique solution, reminiscent of the problem of finding a transport map between two distributions. A unique control law can be identified by introducing control cost functions, that are motivated by the optimal transportation problem or Schr\"odinger bridge problem. The objective of this paper is to study the relationship between optimality and long-term stability of a family of exact control laws. Remarkably, the control law that is optimal in the optimal transportation sense leads to an EnKF algorithm that is not stable.

We consider the problem of steering a linear stochastic system between two end-point degenerate Gaussian distributions in finite time. This accounts for those situations in which some but not all of the state entries are uncertain at the initial, t = 0, and final time, t = T . This problem entails non-trivial technical challenges as the singularity of terminal state-covariance causes the control to grow unbounded at the final time T. Consequently, the entropic interpolation (Schroedinger Bridge) is provided by a diffusion process which is not finite-energy, thereby placing this case outside of most of the current theory. In this paper, we show that a feasible interpolation can be derived as a limiting case of earlier results for non-degenerate cases, and that it can be expressed in closed form. Moreover, we show that such interpolation belongs to the same reciprocal class of the uncontrolled evolution. By doing so we also highlight a time-symmetry of the problem, contrasting dual formulations in the forward and reverse time-directions, where in each the control grows unbounded as time approaches the end-point (in the forward and reverse time-direction, respectively)., Comment: 8 pages

Function theory on the unit disc proved key to a range of problems in statistics, probability theory, signal processing literature, and applications, and in this, a special place is occupied by trigonometric functions and the Fejer-Riesz theorem that non-negative trigonometric polynomials can be expressed as the modulus of a polynomial of the same degree evaluated on the unit circle. In the present note we consider a natural generalization of non-negative trigonometric polynomials that are matrix-valued with specified non-trivial poles (i.e., other than at the origin or at infinity). We are interested in the corresponding spectral factors and, specifically, we show that the factorization of trigonometric polynomials can be carried out in complete analogy with the Fejer-Riesz theorem. The affinity of the factorization with the Fejer-Riesz theorem and the contrast to classical spectral factorization lies in the fact that the spectral factors have degree smaller than what standard construction in factorization theory would suggest. We provide two juxtaposed proofs of this fundamental theorem, albeit for the case of strict positivity, one that relies on analytic interpolation theory and another that utilizes classical factorization theory based on the Yacubovich-Popov-Kalman (YPK) positive-real lemma., Comment: 11 pages

In 1931/32, Schroedinger studied a hot gas Gedankenexperiment, an instance of large deviations of the empirical distribution and an early example of the so-called maximum entropy inference method. This so-called Schroedinger bridge problem (SBP) was recently recognized as a regularization of the Monge-Kantorovich Optimal Mass Transport (OMT), leading to effective computation of the latter. Specifically, OMT with quadratic cost may be viewed as a zero-temperature limit of SBP, which amounts to minimization of the Helmholtz's free energy over probability distributions constrained to possess given marginals. The problem features a delicate compromise, mediated by a temperature parameter, between minimizing the internal energy and maximizing the entropy. These concepts are central to a rapidly expanding area of modern science dealing with the so-called {\em Sinkhorn algorithm} which appears as a special case of an algorithm first studied by the French analyst Robert Fortet in 1938/40 specifically for Schroedinger bridges. Due to the constraint on end-point distributions, dynamic programming is not a suitable tool to attack these problems. Instead, Fortet's iterative algorithm and its discrete counterpart, the Sinkhorn iteration, permit computation by iteratively solving the so-called {\em Schroedinger system}. In both the continuous as well as the discrete-time and space settings, {\em stochastic control} provides a reformulation and dynamic versions of these problems. The formalism behind these control problems have attracted attention as they lead to a variety of new applications in spacecraft guidance, control of robot or biological swarms, sensing, active cooling, network routing as well as in computer and data science. This multifacet and versatile framework, intertwining SBP and OMT, provides the substrate for a historical and technical overview of the field taken up in this paper., Comment: 67 pages

The shortest path problem is formulated as an $l_1$-regularized regression problem, known as lasso. Based on this formulation, a connection is established between Dijkstra's shortest path algorithm and the least angle regression (LARS) for the lasso problem. Specifically, the solution path of the lasso problem, obtained by varying the regularization parameter from infinity to zero (the regularization path), corresponds to shortest path trees that appear in the bi-directional Dijkstra algorithm. Although Dijkstra's algorithm and the LARS formulation provide exact solutions, they become impractical when the size of the graph is exceedingly large. To overcome this issue, the alternating direction method of multipliers (ADMM) is proposed to solve the lasso formulation. The resulting algorithm produces good and fast approximations of the shortest path by sacrificing exactness that may not be absolutely essential in many applications. Numerical experiments are provided to illustrate the performance of the proposed approach., Comment: 17 pages

Spectral PCA (sPCA), in contrast to classical PCA, offers the advantage of identifying organized spatio-temporal patterns within specific frequency bands and extracting dynamical modes. However, the unavoidable tradeoff between frequency resolution and robustness of the PCs leads to high sensitivity to noise and overfitting, which limits the interpretation of the sPCA results. We propose herein a simple non-parametric implementation of the sPCA using the continuous analytic Morlet wavelet as a robust estimator of the cross-spectral matrices with good frequency resolution. To improve the interpretability of the results when several modes of similar amplitude exist within the same frequency band, we propose a rotation of eigenvectors that optimizes the spatial smoothness in the phase domain. The developed method, called rotated spectral PCA (rsPCA), is tested on synthetic data simulating propagating waves and shows impressive performance even with high levels of noise in the data. Applied to historical sea surface temperature (SST) time series over the Pacific Ocean, the method accurately captures the El Ni\~{n}o-Southern Oscillation (ENSO) at low frequency (2 to 7 years periodicity). At high frequencies (sub-annual periodicity), at which several extratropical patterns of similar amplitude are identified, the rsPCA successfully unmixes the underlying modes, revealing spatially coherent patterns with robust propagation dynamics. Identification of higher frequency space-time climate modes holds promise for seasonal to subseasonal prediction and for diagnostic analysis of climate models., Comment: 25 pages

We seek a generalization of regression and principle component analysis (PCA) in a metric space where data points are distributions metrized by the Wasserstein metric. We recast these analyses as multimarginal optimal transport problems. The particular formulation allows efficient computation, ensures existence of optimal solutions, and admits a probabilistic interpretation over the space of paths (line segments). Application of the theory to the interpolation of empirical distributions, images, power spectra, as well as assessing uncertainty in experimental designs, is envisioned.

The analysis of networks, aimed at suitably defined functionality, often focuses on partitions into subnetworks that capture desired features. Chief among the relevant concepts is a 2-partition, that underlies the classical Cheeger inequality, and highlights a constriction (bottleneck) that limits accessibility between the respective parts of the network. In a similar spirit, the purpose of the present work is to introduce a new concept of maximal global circulation and to explore 3-partitions that expose this type of macroscopic feature of networks. Herein, graph circulation is motivated by transportation networks and probabilistic flows (Markov chains) on graphs. Our goal is to quantify the large-scale imbalance of network flows and delineate key parts that mediate such global features. While we introduce and propose these notions in a general setting, in this paper, we only work out the case of planar graphs. We explain that a scalar potential can be identified to encapsulate the concept of circulation, quite similarly as in the case of the curl of planar vector fields. Beyond planar graphs, in the general case, the problem to determine global circulation remains at present a combinatorial problem., Comment: 20 pages, 11 figures

Classical thermodynamics aimed to quantify the efficiency of thermodynamic engines by bounding the maximal amount of mechanical energy produced compared to the amount of heat required. While this was accomplished early on, by Carnot and Clausius, the more practical problem to quantify limits of power that can be delivered, remained elusive due to the fact that quasistatic processes require infinitely slow cycling, resulting in a vanishing power output. Recent insights, drawn from stochastic models, appear to bridge the gap between theory and practice in that they lead to physically meaningful expressions for the dissipation cost in operating a thermodynamic engine over a finite time window. Building on this framework of {\em stochastic thermodynamics} we derive bounds on the maximal power that can be drawn by cycling an overdamped ensemble of particles via a time-varying potential while alternating contact with heat baths of different temperature ($T_c$ cold, and $T_h$ hot). Specifically, assuming a suitable bound $M$ on the spatial gradient of the controlling potential, we show that the maximal achievable power is bounded by $\frac{M}{8}(\frac{T_h}{T_c}-1)$. Moreover, we show that this bound can be reached to within a factor of $(\frac{T_h}{T_c}-1)/(\frac{T_h}{T_c}+1)$ by operating the cyclic thermodynamic process with a quadratic potential., Comment: 24 pages, 1 figure, 1 table

This paper contributes to the emerging viewpoint that governing equations for dynamic state estimation, conditioned on the history of noisy measurements, can be viewed as gradient flow on the manifold of joint probability density functions with respect to suitable metrics. Herein, we focus on the Wonham filter where the prior dynamics is given by a continuous time Markov chain on a finite state space; the measurement model includes noisy observation of the (possibly nonlinear function of) state. We establish that the posterior flow given by the Wonham filter can be viewed as the small time-step limit of proximal recursions of certain functionals on the probability simplex. The results of this paper extend our earlier work where similar proximal recursions were derived for the Kalman-Bucy filter.

We formulate a new class of two-person zero-sum differential games, in a stochastic setting, where a specification on a target terminal state distribution is imposed on the players. We address such added specification by introducing incentives to the game that guides the players to steer the join distribution accordingly. In the present paper, we only address linear quadratic games with Gaussian target distribution. The solution is characterized by a coupled Riccati equations system, resembling that in the standard linear quadratic differential games. Indeed, once the incentive function is calculated, our problem reduces to a standard one. Tthe framework developed in this paper extends previous results in covariance control, a fast growing research area. On the numerical side, problems herein are reformulated as convex-concave minimax problems for which efficient and reliable algorithms are available., Comment: 10 pages

Advanced measurement techniques and high performance computing have made large data sets available for a wide range of turbulent flows that arise in engineering applications. Drawing on this abundance of data, dynamical models can be constructed to reproduce structural and statistical features of turbulent flows, opening the way to the design of effective model-based flow control strategies. This review describes a framework for completing second-order statistics of turbulent flows by models that are based on the Navier-Stokes equations linearized around the turbulent mean velocity. Systems theory and convex optimization are combined to address the inherent uncertainty in the dynamics and the statistics of the flow by seeking a suitable parsimonious correction to the prior linearized model. Specifically, dynamical couplings between states of the linearized model dictate structural constraints on the statistics of flow fluctuations. Thence, colored-in-time stochastic forcing that drives the linearized model is sought to account for and reconcile dynamics with available data (i.e., partially known second order statistics). The number of dynamical degrees of freedom that are directly affected by stochastic excitation is minimized as a measure of model parsimony. The spectral content of the resulting colored-in-time stochastic contribution can alternatively be seen to arise from a low-rank structural perturbation of the linearized dynamical generator, pointing to suitable dynamical corrections that may account for the absence of the nonlinear interactions in the linearized model., Comment: To appear in the Annual Review of Control, Robotics, and Autonomous Systems

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., Comment: 10 pages, 8 figures