On Convergence of Extended Dynamic Mode Decomposition to the Koopman Operator

By Milan Korda, Igor Mezi'c. 2017

491 citations recorded by the source corpus.

Extended dynamic mode decomposition (EDMD) (Williams et al. in J Nonlinear Sci 25(6):1307–1346, 2015) is an algorithm that approximates the action of the Koopman operator on an N-dimensional subspace of the space of observables by sampling at M points in the state space. Assuming that the samples are drawn either independently or ergodically from some measure $$\mu $$μ, it was shown in Klus et al. (J Comput Dyn 3(1):51–79, 2016) that, in the limit as $$M\rightarrow \infty $$M→∞, the EDMD operator $$\mathcal {K}_{N,M}$$KN,M converges to $$\mathcal {K}_N$$KN, where $$\mathcal {K}_N$$KN is the $$L_2(\mu )$$L2(μ)-orthogonal projection of the action of the Koopman operator on the finite-dimensional subspace of observables. We show that, as $$N \rightarrow \infty $$N→∞, the operator $$\mathcal {K}_N$$KN converges in the strong operator topology to the Koopman operator. This in particular implies convergence of the predictions of future values of a given observable over any finite time horizon, a fact important for practical applications such as forecasting, estimation and control. In addition, we show that accumulation points of the spectra of $$\mathcal {K}_N$$KN correspond to the eigenvalues of the Koopman operator with the associated eigenfunctions converging weakly to an eigenfunction of the Koopman operator, provided that the weak limit of the eigenfunctions is nonzero. As a by-product, we propose an analytic version of the EDMD algorithm which, under some assumptions, allows one to construct $$\mathcal {K}_N$$KN directly, without the use of sampling. Finally, under additional assumptions, we analyze convergence of $$\mathcal {K}_{N,N}$$KN,N (i.e., $$M=N$$M=N), proving convergence, along a subsequence, to weak eigenfunctions (or eigendistributions) related to the eigenmeasures of the Perron–Frobenius operator. No assumptions on the observables belonging to a finite-dimensional invariant subspace of the Koopman operator are required throughout.

Subfields: Aerospace Engineering, Computational Mechanics, Statistical and Nonlinear Physics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Aerospace Engineering

In Computational Mechanics

In Statistical and Nonlinear Physics

Citations in the corpus

Deep Generative Markov State Models (2018, background): “In practice, the long-time behavior of dynamical systems can be accurately described in a Markovian model when suitable features or variables are used, and when the time resolution of the model is sufficiently coarse such that the time-evolution can be represented with a manageable number of dynamic”
Koopman Lyapunov‐based model predictive control of nonlinear chemical process systems (2019, background): “Nevertheless, the convergence of EDMD approximations has been recently established under the assumption that the dimension of the subspace N approaches infinity.(32) Therefore, this error can be made arbitrarily small by considering a large set of basis functions.”
Extended dynamic mode decomposition with dictionary learning: A data-driven adaptive spectral decomposition of the Koopman operator. (2017, background): “It is well-known that the choice signiﬁcantly impacts the approximation quality of the spectral properties of the system 22–24 .”
Resurrecting Recurrent Neural Networks for Long Sequences (2023, methodology): “Our notation and results are based on Korda and Mezić (2018); Mauroy et al. (2020).”
On Numerical Approximations of the Koopman Operator (2020, background): “As a consequence of this approach, we show how the concept of a weak eigenfunction, first discussed in [37], arises.”
Linear predictors for nonlinear dynamical systems: Koopman operator meets model predictive control (2016, methodology): “ the EDMD algorithm of Section 3.2. Full exposition of the theoretical analysis of EDMD is beyond the scope of this paper and therefore we only summarize the authors’ results obtained concurrently in [11], where the reader is referred to for proofs of the theorems stated in this section and addition”
Variational Approach for Learning Markov Processes from Time Series Data (2017, background): “As shown in [28], this approximation becomes exact in the limit of infinitely-sized feature transformations with f = g, and a similar conclusion can also be obtained when f ,g are infinite-dimensional feature functions deduced from a characteristic kernel [56].”
Data-driven approximation of the Koopman generator: Model reduction, system identification, and control (2019, background): “The convergence of the standard EDMD approximation to the Koopman operator as the number of basis functions goes to inﬁnity is discussed in [39].”
Data-driven spectral analysis of the Koopman operator (2017, methodology): “On the other hand, the DMD-like methods do not require the knowledge of the eigenvalues beforehand but their spectral convergence properties are not as favorable [19] and similarly to averaging methods they do not systematically handle the continuous part of the spectrum.”