Koopman modes / Dynamic mode decomposition

The Dynamic Mode Decomposition is a procedure for estimating the eigenvectors and eigenvalues of the Koopman operator. The latter provides a means by which the dynamics of a flow can be analysed, this analysis being effected through some associated observable. An assumption central to the approach is that the flow can be considered as a dynamical system evolving on a manifold D of dimension N. A manifold—the locus of points that comprise the state-space trajectory of a dynamical system—is a gener­alisation, to the non-linear case, of the eigenspace associated with the linear instability of dynamical system in the vicinity of a fixed point : while in a linearised system eigenvectors denote the directions in which that system will move, exponentially, either to or from a fixed point (or equilibrium point), in the non-linear context the manifold amounts to a continuation of these eigenvectors, which continually change direction as the system evolves non-linearly.

This section provides an introduction to both the Koopman operator and the dynamic mode decomposition. The exposition combines elements taken from Rowley et al. (2009), Schmid (2010) and Pastur (2011).

The Koopman operator Let X be a point on D, corresponding to the state of the system at some given time, and let ft be a propagator (frequently referred to as a ‘flow’ or a ‘map’ in dynamical systems or control theory textbooks) that evolves, propagates, or maps, the flow from one time-step to the next; i. e. from X(t0) Є D to X(t0 +1) Є D: 17

X (to +1) = ft {X (to)}. (152)

In an experiment we never have access to the full flow state; at best we may have access to the velocity field on a two-dimensional spatial section (from a PIV measurement for example), with restricted temporal resolution, or single-point information with higher temporal resolution (from a hot-wire, Laser Doppler Velocimeter or microphone for instance). Such an incomplete sample of the flow can be referred to as an observable. We denote this observation by means of a function, q(X), which gives us the observable

7 In the case of fluid flow the propagator is the right hand side of the Navier Stokes equations; i. e. the dynamic law governing the time evolution of the fluid flow.

corresponding to the full state X. q belongs to a Hilbert space, H, and so we can define the norm:

\q\ = v/qqb = у J q2 < ж. (153)

The Koopman operator, Ut, acts in H, such that:

Ut{q(X)} = q(ft[X}). (154)

In other words, the Koopman operator is a map that describes the evolution of the observable, q (which is a function of the full flow state X), from one time-step to the next. The non-linear dynamics associated with the evolu­tion of the full flow leaves its signature in the evolution of the observable; the essence of Koopman/DMD analysis is here: by considering the evolu­tion of the observable we seek to gain insight regarding the nature of the evolution law that underpins the dynamics of the full flow.

The Koopman operator has the following important property. Let фj and Xj be, respectively, eigenfunctions and associated eigenvalues of Ut.[20] If we denote by Xk the state of the system at some time kAt after an initial time t0: Xk = X(to + kAt), then:

The first equality simply corresponds to the definition of the Koopman operator—it evolves the observable, q, from its value when the system is in the state Xk to its value when the system is in the state Xk+1. In the second equality the observable, q, has been expanded in terms of the eigenfunctions of the Koopman operator (chosen here as a suitable set of basis functions); Vj are the associated expansion coefficients, obtained by projecting the ob­servable, q, onto the eigenfunctions, hj. In the third equality the Koopman operator has simply been moved inside the summation, while in the fourth, as hj are eigenfunctions of U, U {hj } can be written as Xjhj.

Vj are the Koopman modes (sometimes referred to as Koopman co­efficients, or dynamic modes), Xj the Koopman eigenvalues and hj the Koopman eigenfunctions. The Dynamic Mode Decomposition constitutes a methodology, similar to the Arnoldi algorithm used in the solution of global stability problems, whereby these quantities can be estimated using limited data sets.

Now, as the evolution of the system from some initial state, Xo to a later state Xk+1 is given by Uк(Xo) (because U(Xk) = UU(Xk-1) = U3(Xk-2) = •••), the state of the observable, q(Xk+1), can be expressed in terms of the state at some initial time, X0, as:

This equation shows that any value of the observable, q, can be deduced from knowledge of the projection of the initial condition q(X0) onto the eigenfunctions, Фі, of the Koopman operator, provided the eigenvalues, Xj are known; this property is important in what follows. Furthermore, if the dynamics considered evolve on a non-degenerated attractor—the dynamics continue to evolve on the manifold, H—then the Koopman operator, U, is a unit operator: the eigenvalues lie on the unit circle and the eigenvectors, Фі, are orthogonal.

Krylov sub-space Consider the following set of successive snapshots of data:

QN-1 = {q(Xo),q(Xi), q(X2), •••, q(XN_i)}, (157)

the sub – and super-scripts on Q indicate the first and last snapshots. Ex­pressed in terms of the Koopman operator this reads:

QN-1 = {q(Xo), U {q(Xo)} , U2 {q(Xo)} , •••, UN-1 {q(Xo)}}, (158)

which is an Ntft-order Krylov subspace. And we know that the Koopman operator applied to this subspace gives:

U {QN-1} = QN : (159)

the action of the Koopman operator is inherently contained in QN.

To this point the observable has been considered a single-point scalar; however, the generalisation to multi-valued observables (for example a ve­locity field obtained from PIV) is straightforward. In this case the Vj are multi-valued and complex.

Dynamic mode decomposition DMD is one possible technique, based on what is known as a companion Matrix, by which the eigenvalues and eigenvectors of U can be estimated; the technique is similar to that used
for the computation of global modes from the Hessenberg matrix using the Arnoldi method.

In what follows we will consider multi-valued observables, represented by the vector q(x, tk). A Krylov subspace is first constructed from sampled data, where the time-step is small enough to resolve all of the dynamics:

Qn-i = {qo, qi, q2,–, qw-i}. (160)

The indices correspond to the successive times, t0,t1,t2, …tN-i. The as­sumption underpinning the companion matrix approach is that the first N fields (where N < M, M being the dimension of the observable q, i. e. the number of spatial points in the snapshot) are sufficient to describe any later realisation of the field q; thus, the Nth snapshot can be expressed as a linear combination of all previous snapshots:

qw = coqo + ciqi + C2q2 + … + cN-iqw-i, (161)

or

qw = QN-ic, (162)

where c = (co, ci, C2,…, cn-i)T and the superscript T denotes hermitian transpose. From equation 158 we know that

u {qN-i} = QN, (163)

i. e. application of the Koopman operator to the Krylov subspace propagates all of the fields by one time-step. In light of this observation, and equation 162, equation 163 can be written as

UQN-i = QN = QN-iC + rT ew, (164)

where C is the companion matrix. eN = (0,0,…, 1)1 Є RN+i and r is a residual vector, orthogonal to the Krylov subspace V0N-i. The residual goes to zero when condition 162 is satisfied.

The following example will help illustrate this. Consider that we have the data:

Qi

where the first and second indices on the matrix entries denote spatial and temporal coordinates, respectively: each column is a snapshot. We know that the Koopman operator, U, will map from Q3 to Q|:

But, we are also making the assumption that qi4 can be expressed as a linear combination of qi4, qi2 and qi3:

414		C1411 + C2421 + C3431
424		C1412 + C2422 + C3432
434		_C1413 + C2 423 + C3433_

Substituting into the previous equation gives, U11 U12 U13′ 411 412 413 412 413 (C1411 + C2412 + C3413) U21 U22 U23 421 422 423 422 423 (C1421 + C2422 + C3423) U31 U32 U33_ 431 432 433 _432 433 (C1431 + C2432 + C3433)_ which is the same as

U11	U12	U13′		411	412	413		411	412	413		0	0	C1
U21	U22	U23		421	422	423		421	422	423		1	0	C2
U31	U32	U33_		431	432	433		431	432	433_		0	1	C3

In the more general case, the companion matrix takes the form:

(165)

DMD consists in computing the eigenmodes of the companion matrix, which are then considered as approximations of the eigenmodes of the Koopman operator (when the residual is zero the correspondence is exact). The matrix C has dimension N x N, and its unknown elements, Cj, can be computed by minimising the norm

N-1 qN -^2 cj qj j=1

min c

copt

2

Having computed the eigenvalues and eigenvectors of the companion matrix we are finally in a position to write

N

Y,2-1 Фз (Xo)v j.

j=1

The initial conditions фj(X0) are obtained by projecting the initial field, qo, on to the Vj. The eigenfunctions, фj, are Fourier modes, фj = exp(iwjt) if the dynamics are periodic.