Search

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 this letter, 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 et al. 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 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.

We derive novel results on the ergodic theory of irreducible, aperiodicMarkov chains. We show how to optimally steer the network flow to a stationarydistribution over a finite or infinite time horizon. Optimality is with respectto an entropic distance between distributions on feasible paths. When the prioris reversible, it shown that solutions to this discrete time and space steeringproblem are reversible as well. A notion of temperature is defined forBoltzmann distributions on networks, and problems analogous to cooling (in thiscase, for evolutions in discrete space and time) are discussed.

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. Indeed, the problem to optimize power can be expressed as a stochastic control problem. Building on this framework of 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 (Tc cold, and Th 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 [Formula presented]. Moreover, we show that this bound can be reached to within a factor of [Formula presented] by operating the cyclic thermodynamic process with a quadratic potential.

Spectral PCA (sPCA), in contrast to classical PCA, offers the advantage of identifying organized spatiotemporal patterns within specific frequency bands and extracting dynamical modes. However, the unavoidable trade-off 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 nonparametric implementation of 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, especially when several modes of similar amplitude exist within the same frequency band, we propose a rotation of the complex-valued eigenvectors to optimize their spatial regularity (smoothness). 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 global historical geopotential height (GPH) and sea surface temperature (SST) daily time series, the method accurately captures patterns of atmospheric Rossby waves at high frequencies (3-60-day periods) in both GPH and SST and El Niño-Southern Oscillation (ENSO) at low frequencies (2-7-yr periodicity) in SST. At high frequencies the rsPCA successfully unmixes the identified waves, revealing spatially coherent patterns with robust propagation dynamics.

We consider the problem of steering a linear stochastic system between two endpoint 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 nontrivial technical challenges, as the singularity of terminal state covariance causes the control to grow unbounded at the final time $T$. Consequently, the entropic interpolation (Schrödinger 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 article, we show that a feasible interpolation can be derived as a limiting case of earlier results for nondegenerate 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 endpoint (in the forward and reverse time direction, respectively).

In 1931-1932, Erwin Schrödinger studied a hot gas Gedankenexperiment (an instance of large deviations of the empirical distribution). Schrödinger's problem represents an early example of a fundamental inference method, the so-called maximum entropy method, having roots in Boltzmann's work and being developed in subsequent years by Jaynes, Burg, Dempster, and Csiszár. The problem, known as the Schrödinger bridge problem (SBP) with "uniform"prior, was more recently recognized as a regularization of the Monge-Kantorovich optimal mass transport (OMT) problem, leading to effective computational schemes for the latter. Specifically, OMT with quadratic cost may be viewed as a zerotemperature limit of the problem posed by Schrödinger in the early 1930s. The latter amounts to minimization of Helmholtz's free energy over probability distributions that are constrained to possess two 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 Sinkhorn algorithm, which appears as a special case of an algorithm first studied in the more challenging continuous space setting by the French analyst Robert Fortet in 1938-1940 specifically for Schrödinger 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 of the optimal solution by iteratively solving the so-called Schrödinger system. Convergence of the iteration is guaranteed by contraction along the steps in suitable metrics, such as Hilbert's projective metric. In both the continuous as well as the discrete time and space settings, stochastic control provides a reformulation of and a context for the dynamic versions of general Schrödinger bridge problems and of their zero-temperature limit, the OMT problem. These problems, in turn, naturally lead to steering problems for flows of one-time marginals which represent a new paradigm for controlling uncertainty. The zero-temperature problem in the continuous-time and space setting turns out to be the celebrated Benamou-Brenier characterization of the McCann displacement interpolation flow in OMT. The formalism and techniques behind these control problems on flows of probability distributions have attracted significant attention in recent years as they lead to a variety of new applications in spacecraft guidance, control of robot or biological swarms, sensing, active cooling, and network routing as well as in computer and data science. This multifaceted and versatile framework, intertwining SBP and OMT, provides the substrate for the historical and technical overview of the field given in this paper. A key motivation has been to highlight links between the classical early work in both topics and the more recent stochastic control viewpoint, which naturally lends itself to efficient computational schemes and interesting generalizations.

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 thermodynamic engines in the idealized case of underdamped particles in the low-friction regime subject to a harmonic potential, 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 shortest path problem is formulated as an l1-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.

This manuscript introduces a regression-type formulation for approximatingthe Perron-Frobenius Operator by relying on distributional snapshots of data.These snapshots may represent densities of particles. The Wasserstein metric isleveraged to define a suitable functional optimization in the space ofdistributions. The formulation allows seeking suitable dynamics so as tointerpolate the distributional flow in function space. A first-order necessarycondition for optimality is derived and utilized to construct a gradient flowapproximating algorithm. The framework is exemplied with numerical simulations.

We consider damped stochastic systems in a controlled (time-varying) 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 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.

Function theory on the unit disc proved key to a range of problems instatistics, probability theory, signal processing literature, and applications,and in this, a special place is occupied by trigonometric functions and theFejer-Riesz theorem that non-negative trigonometric polynomials can beexpressed as the modulus of a polynomial of the same degree evaluated on theunit circle. In the present note we consider a natural generalization ofnon-negative trigonometric polynomials that are matrix-valued with specifiednon-trivial poles (i.e., other than at the origin or at infinity). We areinterested in the corresponding spectral factors and, specifically, we showthat the factorization of trigonometric polynomials can be carried out incomplete analogy with the Fejer-Riesz theorem. The affinity of thefactorization with the Fejer-Riesz theorem and the contrast to classicalspectral factorization lies in the fact that the spectral factors have degreesmaller than what standard construction in factorization theory would suggest.We provide two juxtaposed proofs of this fundamental theorem, albeit for thecase of strict positivity, one that relies on analytic interpolation theory andanother that utilizes classical factorization theory based on theYacubovich-Popov-Kalman (YPK) positive-real lemma.

The analysis of networks, aimed at suitably defined functionality, oftenfocuses on partitions into subnetworks that capture desired features. Chiefamong the relevant concepts is a 2-partition, that underlies the classicalCheeger inequality, and highlights a constriction (bottleneck) that limitsaccessibility 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 globalcirculation and to explore 3-partitions that expose this type of macroscopicfeature of networks. Herein, graph circulation is motivated by transportationnetworks and probabilistic flows (Markov chains) on graphs. Our goal is toquantify the large-scale imbalance of network flows and delineate key partsthat mediate such global features. While we introduce and propose these notionsin a general setting, in this paper, we only work out the case of planargraphs. We explain that a scalar potential can be identified to encapsulate theconcept of circulation, quite similarly as in the case of the curl of planarvector fields. Beyond planar graphs, in the general case, the problem todetermine global circulation remains at present a combinatorial problem.

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 letter 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 dependencies can only be ascertained by considering stochastic models at this finest time scale, which in general is faster than the observational sampling rate.

We construct certain matricial analogues of mass transport for positive-definite matrices of equal trace. The framework aims to devise ways of interpolating positive-definite matrices that tradeoff between 'aligning up their eigenstructure' and 'scaling the corresponding eigenvalues.' Motivation for the work is provided by power spectral analysis of multivariate time series where linear interpolation between matrix-valued power spectra generates push-pop unrealistic and undesirable artifacts.

We introduce the problem of transporting vector-valued distributions. In this, a salient feature is that mass may ow 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 color image processing, multimodality imaging, polarimetric radar, as well as network problems where resources may be vectorial.

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 to that of probability measures, using the framework of optimal transport.

The purpose of this work is to pose and solve the problem to guide acollection of weakly interacting dynamical systems (agents, particles, etc.) toa specified terminal distribution. The framework is that of mean-field and ofcooperative games. A terminal cost is used to accomplish the task; we establishthat the map between terminal costs and terminal probability distributions isonto. Our approach relies on and extends the theory of optimal mass transportand its generalizations.

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 continuous-time smoothing and interpolation, providing a definitive unification of these concepts. The absence of data over subintervals requires in general a hybrid filtering approach involving both continuous-time and discrete-time filtering steps.

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 (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.

We develop an approach to the spectral estimation that has been advocated by [A. Ferrante et al., 'Time and spectral domain relative entropy: A new approach to multivariate spectral estimation,' IEEE Trans. Autom. Control, vol. 57, no. 10, pp. 2561-2575, Oct. 2012.] and, in the context of the scalar-valued covariance extension problem, by [P. Enqvist and J. Karlsson, 'Minimal itakura-saito distance and covariance interpolation,' in Proc. 47th IEEE Conf. Decision Control, 2008, pp. 137-142]. 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 this 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.

We take a new look at the relation between the optimal transport problem and the Schrödinger bridge problem from a stochastic control perspective. Our aim is to highlight new connections between the two that are richer and deeper than those previously described in the literature. We begin with an elementary derivation of the Benamou–Brenier fluid dynamic version of the optimal transport problem and provide, in parallel, a new fluid dynamic version of the Schrödinger bridge problem. We observe that the latter establishes an important connection with optimal transport without zero-noise limits and solves a question posed by Eric Carlen in 2006. Indeed, the two variational problems differ by a Fisher information functional. We motivate and consider a generalization of optimal mass transport in the form of a (fluid dynamic) problem of optimal transport with prior. This can be seen as the zero-noise limit of Schrödinger bridges when the prior is any Markovian evolution. We finally specialize to the Gaussian case and derive an explicit computational theory based on matrix Riccati differential equations. A numerical example involving Brownian particles is also provided.

We consider the problem of steering a linear dynamical system with complete 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 explicitly by solving a pair of differential Lyapunov equations that are nonlinearly coupled through their boundary values. This result, given its attractive algorithmic nature, appears to have several potential applications such as to quality control, control of industrial processes, as well 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 the present case of steering a linear stochastic system constitutes such a Schrödinger bridge for possibly degenerate diffusions. Our results provide the first implementable form of the optimal control for a general Gauss-Markov process. Illustrative examples are provided for steering inertial particles and for "cooling" a stochastic oscillator. 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. A second part to this work, that is to appear as part II, addresses the general situation where the stochastic excitation enters through channels that may differ from those used to control.

We present a particular formulation of optimal transport for matrix-valued density functions. Our aim is to devise a geometry which is suitable for comparing power spectral densities of multivariable time series. More specifically, the value of a power spectral density at a given frequency, which in the matricial case encodes power as well as directionality, is thought of as a proxy for a "matrix-valued mass density." Optimal transport aims at establishing a natural metric in the space of such matrix-valued densities which takes into account differences between power across frequencies as well as misalignment of the corresponding principle axes. Thus, our transportation cost includes a cost of transference of power between frequencies together with a cost of rotating the principle directions of matrix densities. The two endpoint matrix-valued densities can be thought of as marginals of a joint matrix-valued density on a tensor product space. This joint density, very much as in the classical Monge-Kantorovich setting, can be thought to specify the transportation plan. Contrary to the classical setting, the optimal transport plan for matrices is no longer supported on a thin zero-measure set.

We present a particular formulation of optimal transport for matrix-valued density functions. Our aim is to devise a geometry which is suitable for comparing power spectral densities of multivariable time series. More specifically, the value of a power spectral density at a given frequency, which in the matricial case encodes power as well as directionality, is thought of as a proxy for a "matrix-valued mass density." Optimal transport aims at establishing a natural metric in the space of such matrix-valued densities which takes into account differences between power across frequencies as well as misalignment of the corresponding principle axes. Thus, our transportation cost includes a cost of transference of power between frequencies together with a cost of rotating the principle directions of matrix densities. The two endpoint matrix-valued densities can be thought of as marginals of a joint matrix-valued density on a tensor product space. This joint density, very much as in the classical Monge-Kantorovich setting, can be thought to specify the transportation plan. Contrary to the classical setting, the optimal transport plan for matrices is no longer supported on a thin zero-measure set.

We address the problem of identifying linear relations among variables based on noisy measurements. This is a central question in the search for structure in large data sets. Often a key assumption is that measurement errors in each variable are independent. This basic formulation has its roots in the work of Charles Spearman in 1904 and of Ragnar Frisch in the 1930s. Various topics such as errors-in-variables, factor analysis, and instrumental variables all refer to alternative viewpoints on this problem and on ways to account for the anticipated way that noise enters the data. In the present paper we begin by describing certain fundamental contributions by the founders of the field and provide alternative modern proofs to certain key results. We then go on to consider a modern viewpoint and novel numerical techniques to the problem. The central theme is expressed by the Frisch-Kalman dictum, which calls for identifying a noise contribution that allows a maximal number of simultaneous linear relations among the noise-free variables-a rank minimization problem. In the years since Frisch's original formulation, there have been several insights, including trace minimization as a convenient heuristic to replace rank minimization. We discuss convex relaxations and theoretical bounds on the rank that, when met, provide guarantees for global optimality. A complementary point of view to this minimum-rank dictum is presented in which models are sought leading to a uniformly optimal quadratic estimation error for the error-free variables. Points of contact between these formalisms are discussed, and alternative regularization schemes are presented.

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. © 2013 IEEE.

We present several natural notions of distance between spectral densityfunctions of (discrete-time) random processes. They are motivated by certainfiltering problems. First we quantify the degradation of performance of apredictor which is designed for a particular spectral density function and thenit is used to predict the values of a random process having a differentspectral density. The logarithm of the ratio between the variance of the error,over the corresponding minimal (optimal) variance, produces a measure ofdistance between the two power spectra with several desirable properties.Analogous quantities based on smoothing problems produce alternative distancesand suggest a class of measures based on fractions of generalized means ofratios of power spectral densities. These distance measures endow the manifoldof spectral density functions with a (pseudo) Riemannian metric. We pursue oneof the possible options for a distance measure, characterize the relevantgeodesics, and compute corresponding distances.

The maximum entropy ansatz, as it is often invoked in the context oftime-series analysis, suggests the selection of a power spectrum which isconsistent with autocorrelation data and corresponds to a random process leastpredictable from past observations. We introduce and compare a class of spectrawith the property that the underlying random process is least predictable atany given point from the complete set of past and future observations. In thiscontext, randomness is quantified by the size of the corresponding smoothingerror and deterministic processes are characterized by integrability of theinverse of their power spectral densities--as opposed to the log-integrabilityin the classical setting. The power spectrum which is consistent with a partialautocorrelation sequence and corresponds to the most random process in this newsense, is no longer rational but generated by finitely many fractional-poles.

Entropy-like functionals on operator algebras have been studied since thepioneering work of von Neumann, Umegaki, Lindblad, and Lieb. The mostwell-known are the von Neumann entropy $trace (\rho\log \rho)$ and ageneralization of the Kullback-Leibler distance $trace (\rho \log \rho - \rho\log \sigma)$, refered to as quantum relative entropy and used to quantifydistance between states of a quantum system. The purpose of this paper is toexplore these as regularizing functionals in seeking solutions tomulti-variable and multi-dimensional moment problems. It will be shown thatextrema can be effectively constructed via a suitable homotopy. The homotopyapproach leads naturally to a further generalization and a description of allthe solutions to such moment problems. This is accomplished by arenormalization of a Riemannian metric induced by entropy functionals. As anapplication we discuss the inverse problem of describing power spectra whichare consistent with second-order statistics, which has been the main motivationbehind the present work.