Abstract
The Koopman operator is a linear but infinite-dimensional operator that governs the evolution of scalar observables defined on the state space of an autonomous dynamical system and is a powerful tool for the analysis and decomposition of nonlinear dynamical systems. In this manuscript, we present a data-driven method for approximating the leading eigenvalues, eigenfunctions, and modes of the Koopman operator. The method requires a data set of snapshot pairs and a dictionary of scalar observables, but does not require explicit governing equations or interaction with a “black box” integrator. We will show that this approach is, in effect, an extension of dynamic mode decomposition (DMD), which has been used to approximate the Koopman eigenvalues and modes. Furthermore, if the data provided to the method are generated by a Markov process instead of a deterministic dynamical system, the algorithm approximates the eigenfunctions of the Kolmogorov backward equation, which could be considered as the “stochastic Koopman operator” (Mezic in Nonlinear Dynamics 41(1–3): 309–325, 2005). Finally, four illustrative examples are presented: two that highlight the quantitative performance of the method when presented with either deterministic or stochastic data and two that show potential applications of the Koopman eigenfunctions.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Bagheri, S.: Effects of weak noise on oscillating flows: linking quality factor, Floquet modes and Koopman spectrum. Phys. Fluids. 26, 094104 (2014)
Bagheri, S.: Koopman-mode decomposition of the cylinder wake. J. Fluid Mech. 726, 596–623 (2013)
Belytschko, T., Krongauz, Y., Organ, D., Fleming, M., Krysl, P.: Meshless methods: an overview and recent developments. Comput. Methods Appl. Mech. Eng. 139(1), 3–47 (1996)
Bishop, C.M., et al.: Pattern Recognition and Machine Learning (Information Science and Statistics), Springer-Verlag, New York (2006)
Bollt, E.M., Santitissadeekorn, N.: Applied and Computational Measurable Dynamics. SIAM, Philadelphia (2013)
Boyd, J.P.: Chebyshev and Fourier Spectral Methods. Courier Dover Publications, New York (2013)
Budišić, M., Mohr, R., Mezić, I.: Applied Koopmanism. Chaos Interdiscip. J. Nonlinear Sci. 22(4), 047510 (2012)
Budisic, M., Mezic, I.: Geometry of the ergodic quotient reveals coherent structures in flows. Phys. D 241, 1255–1269 (2012)
Chen, K.K., Tu, J.H., Rowley, C.W.: Variants of dynamic mode decomposition: boundary condition, Koopman, and Fourier analyses. J. Nonlinear Sci. 22(6), 887–915 (2012)
Coifman, R.R., Lafon, S.: Diffusion maps. Appl. Comput. Harmonic Anal. 21(1), 5–30 (2006)
Dean, J., Ghemawat, S.: MapReduce: simplified data processing on large clusters. Commun. ACM 51(1), 107–113 (2008)
Dellnitz, M., Froyland, G., Junge, O.: The algorithms behind GAIO—set oriented numerical methods for dynamical systems. In: Bernold Fiedler (ed.) Ergodic Theory, Analysis, and Efficient Simulation of Dynamical Systems, pp. 145–174, Springer, Berlin (2001)
Dsilva, C.J., Talmon, R., Rabin, N., Coifman, R.R., Kevrekidis, I.G.: Nonlinear intrinsic variables and state reconstruction in multiscale simulations. J. Chem. Phys. 139(18), 184109 (2013)
Eisenhower, B., Maile, T., Fischer, M., Mezić, I.: Decomposing building system data for model validation and analysis using the Koopman operator. In: Proceedings of the National IBPSAUSA Conference, New York, USA (2010)
Erban, R., Frewen, T.A., Wang, X., Elston, T.C., Coifman, R., Nadler, B., Kevrekidis, I.G.: Variable-free exploration of stochastic models: a gene regulatory network example. J. Chem. Phys. 126(15), 155103 (2007)
Froyland, G., Gottwald, G.A., Hammerlindl, A.: A computational method to extract macroscopic variables and their dynamics in multiscale systems. SIAM J. Appl. Dyn. Sys. 13(4), 1816–1846 (2014)
Froyland, G.: Statistically optimal almost-invariant sets. Phys. D Nonlinear Phenom. 200(3), 205–219 (2005)
Froyland, G., Padberg, K., England, M.H., Treguier, A.M.: Detection of coherent oceanic structures via transfer operators. Phys. Rev. Lett. 98(22), 224503 (2007)
Froyland, G., Padberg, K.: Almost-invariant sets and invariant manifolds—connecting probabilistic and geometric descriptions of coherent structures in flows. Phys. D Nonlinear Phenom. 238(16), 1507–1523 (2009)
Gaspard, P., Nicolis, G., Provata, A., Tasaki, S.: Spectral signature of the pitchfork bifurcation: Liouville equation approach. Phys. Rev. E 51(1), 74 (1995)
Gaspard, P., Tasaki, S.: Liouvillian dynamics of the Hopf bifurcation. Phys. Rev. E 64(5), 056232 (2001)
Givon, D., Kupferman, R., Stuart, A.: Extracting macroscopic dynamics: model problems and algorithms. Nonlinearity 17(6), R55 (2004)
Hansen, P.C.: Truncated singular value decomposition solutions to discrete ill-posed problems with ill-determined numerical rank. SIAM J. Sci. Stat. Comput. 11(3), 503–518 (1990)
Higham, D.J.: An algorithmic introduction to numerical simulation of stochastic differential equations. SIAM Rev. 43(3), 525–546 (2001)
Hirsch, C.: Numerical computation of internal and external flows: The fundamentals of computational fluid dynamics vol. 1, Butterworth-Heinemann (2007)
Holmes, P., Lumley, J.L., Berkooz, G.: Turbulence, Coherent Structures, Dynamical Systems and Symmetry. Cambridge University Press, Cambridge (1998)
Jovanović, M.R., Schmid, P.J., Nichols, J.W.: Sparsity-promoting dynamic mode decomposition. Phys. Fluids 26, 024103 (2014)
Juang, J.-N.: Applied System Identification. Prentice Hall, Englewood Cliffs (1994)
Karniadakis, G., Sherwin, S.: Spectral/Hp Element Methods for Computational Fluid Dynamics. Oxford University Press, Oxford (2013)
Kloeden, P.E., Platen, E.: Numerical solution of stochastic differential equations. Springer, Berlin (1992)
Koopman, B.O.: Hamiltonian systems and transformation in Hilbert space. Proc. Natl. Acad. Sci. U. S. A. 17(5), 315 (1931)
Koopman, B.O., Neumann, J.V.: Dynamical systems of continuous spectra. Proc. Natl. Acad. Sci. U. S. A. 18(3), 255 (1932)
Lee, J.A., Verleysen, M.: Nonlinear Dimensionality Reduction. Springer, Berlin (2007)
Lehoucq, R.B., Sorensen, D.C., Yang, C.: ARPACK users’ guide: Solution of large-scale eigenvalue problems. SIAM, Philadelphia (1998)
Liu, G.-R.: Meshfree methods: Moving beyond the finite element method. CRC Press, Boca Raton (2010)
Matkowsky, B., Schuss, Z.: Eigenvalues of the Fokker-Planck operator and the approach to equilibrium for diffusions in potential fields. SIAM J. Appl. Math. 40(2), 242–254 (1981)
Mauroy, A., Mezic, I.: A spectral operator-theoretic framework for global stability. In: Decision and Control (CDC), 2013 IEEE 52nd Annual Conference on, pp. 5234–5239 (2013)
Mauroy, A., Mezić, I., Moehlis, J.: Isostables, isochrons, and Koopman spectrum for the action-angle representation of stable fixed point dynamics. Phys. D Nonlinear Phenom. 261, 19–30 (2013)
Mauroy, A., Mezić, I.: On the use of Fourier averages to compute the global isochrons of (quasi) periodic dynamics. Chaos Interdiscip. J. Nonlinear Sci. 22(3), 033112 (2012)
Mezić, I.: Spectral properties of dynamical systems, model reduction and decompositions. Nonlinear Dyn. 41(1–3), 309–325 (2005)
Monaghan, J.J.: Smoothed particle hydrodynamics. Annu. Rev. Astron. Astrophys. 30, 543–574 (1992)
Muld, T.W., Efraimsson, G., Henningson, D.S.: Flow structures around a high-speed train extracted using proper orthogonal decomposition and dynamic mode decomposition. Comput. Fluids 57, 87–97 (2012)
Nadler, B., Lafon, S., Kevrekidis, I.G., Coifman, R.R.: Diffusion maps, spectral clustering and eigenfunctions of Fokker-Planck operators. Adv Neural Inf Process Syst. 18, 955–962 (2005)
Nadler, B., Lafon, S., Coifman, R.R., Kevrekidis, I.G.: Diffusion maps, spectral clustering and reaction coordinates of dynamical systems. Appl. Comput. Harmonic Anal. 21(1), 113–127 (2006)
Rowley, C.W., Mezić, I., Bagheri, S., Schlatter, P., Henningson, D.S.: Spectral analysis of nonlinear flows. J. Fluid Mech. 641, 115–127 (2009)
Santitissadeekorn, N., Bollt, E.: The infinitesimal operator for the semigroup of the Frobenius-Perron operator from image sequence data: vector fields and transport barriers from movies. Chaos Interdiscip. J. Nonlinear Sci. 17(2), 023126 (2007)
Schmid, P.J.: Dynamic mode decomposition of numerical and experimental data. J. Fluid Mech. 65(6), 5–28 (2010)
Schmid, P., Li, L., Juniper, M., Pust, O.: Applications of the dynamic mode decomposition. Theor. Comput. Fluid Dyn. 25(1–4), 249–259 (2011)
Schmid, P.J., Violato, D., Scarano, F.: Decomposition of time-resolved tomographic PIV. Exp. Fluids 52(6), 1567–1579 (2012)
Seena, A., Sung, H.J.: Dynamic mode decomposition of turbulent cavity flows for self-sustained oscillations. Int. J. Heat Fluid Flow 32(6), 1098–1110 (2011)
Sirisup, S., Karniadakis, G.E., Xiu, D., Kevrekidis, I.G.: Equation-free/Galerkin-free POD-assisted computation of incompressible flows. J. Comput. Phys. 207(2), 568–587 (2005)
Stengel, R.F.: Optimal Control and Estimation. Courier Dover Publications, New York (2012)
Susuki, Y., Mezic, I.: Nonlinear Koopman modes and power system stability assessment without models. IEEE Trans. Power Syst. 29(2), 899–907 (2014)
Susuki, Y., Mezić, I.: Nonlinear Koopman modes and coherency identification of coupled swing dynamics. IEEE Trans. Power Syst. 26(4), 1894–1904 (2011)
Susuki, Y., Mezić, I.: Nonlinear Koopman modes and a precursor to power system swing instabilities. Power Syst. IEEE Trans. 27(3), 1182–1191 (2012)
Todorov, E.: Optimal control theory. In: Bayesian brain: Probabilistic approaches to neural coding, Kenji Doya (Editor), pp. 269–298. MIT Press, Cambridge (2007)
Trefethen, L.N.: Spectral Methods in MATLAB, vol. 10. SIAM, Philadelphia (2000)
Tu, J.H., Rowley, C.W., Luchtenburg, D.M., Brunton, S.L., Kutz, J.N.: On dynamic mode decomposition: Theory and applications. J Comput Dyn. 1(2), 391–421 (2014)
Wendland, H.: Meshless Galerkin methods using radial basis functions. Math. Comput. Am. Math. Soc. 68(228), 1521–1531 (1999)
Wynn, A., Pearson, D., Ganapathisubramani, B., Goulart, P.: Optimal mode decomposition for unsteady flows. J. Fluid Mech. 733, 473–503 (2013)
Acknowledgments
The authors would like to thank Igor Mezić, Jonathan Tu, Maziar Hemati, and Scott Dawson for interesting and useful discussions on dynamic mode decomposition and the Koopman operator. M.O.W. gratefully acknowledges support from NSF DMS-1204783. I.G.K acknowledges support from AFOSR FA95550-12-1-0332 and NSF CMMI-1310173. C.W.R acknowledges support from AFOSR FA9550-12-1-0075.
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Oliver Junge.
Appendix: EDMD with Redundant Dictionaries
Appendix: EDMD with Redundant Dictionaries
In this appendix, we present a simple example of applying EDMD to a problem where the elements of \({\mathcal {D}}\) contain redundancies (i.e., the elements of \({\mathcal {D}}\) are not a basis for \({\mathcal {F}}_{{\mathcal {D}}} \subset {\mathcal {F}}\)). Given full knowledge of the underlying dynamical system, one would always choose the elements of \({\mathcal {D}}\) to be a basis for \({\mathcal {F}}_{{\mathcal {D}}}\), but due to our ignorance of \({\mathcal {M}}\), a redundant set of functions may be chosen. Our objective here is to demonstrate that accurate results can still be obtained even if such a choice is made. To separate quadrature errors from errors resulting from our choice of \({\mathcal {D}}\), we assume that M is large enough that the EDMD method has already converged to a Galerkin method in that the residual is orthogonal to the space spanned by \({\mathcal {D}}\).
For the purposes of demonstration, we replace \(\mathcal {K}\) with \(\mathcal {L}=\partial _s^2\), the Laplace–Beltrami operator defined on the manifold \({\mathcal {M}}\), where \((x,y) = (s, s)\) for \(s\in [0, 2\pi )\) with periodic boundary conditions, which would correspond to, say, the EDMD procedure applied to a diffusion process on a periodic domain. A useful basis for this problem would be \(\tilde{\psi }_k(x,y) = \exp (\imath ks) = \exp (\imath k(x+y))\), but without prior knowledge of \({\mathcal {M}}\), it is difficult to determine this choice should be made. Because the problem appears two-dimensional, one may choose a dictionary whose elements have the form \(\psi _{m, n}(x, y) = \exp (\imath m x + \imath ny)\), which contains the \(\tilde{\psi }\) but is not linearly independent on \({\mathcal {M}}\). The indexes we use for the set of functions are \(\psi _k(x,y) = \psi _{m, n}(x,y)\) with \(m = (k \mod K) - K/2\) and \(n = \left\lfloor \frac{k}{K}\right\rfloor - K/2\) with \(k = 0, 1, \ldots , K^2\). Here, \(K\in \mathbb {N}\) is the total number of basis functions in a single spatial dimension.
Following (12), the i, jth element of \(\varvec{G}\) is
Similarly,
The diagonal structure we would normally have has been replaced with a more complex sparsity pattern, and it has a large nullspace (when \(K=8\), the nullspace is 50-dimensional). To reiterate, there are no advantages to this choice; the redundancies in \({\mathcal {D}}\) appear due to ignorance about the nature of \({\mathcal {M}}\), which is the expected situation. Because \(\varvec{G}\) is singular, the use of the pseudoinverse in (12) is critical to obtain a unique solution.
However, once this is done, there is excellent agreement between the leading eigenfunctions and eigenvalues of \(\mathcal {L}\) and those computed using EDMD; this is shown in Fig. 14. The nonzero eigenvalues are quantitatively correct; in particular, pairs of eigenvalues of the form \(\lambda =-k^2\) are obtained up until \(k=8\) using \(K = 8\). Although the maximum (absolute) value of m or n is only 4, it is clear that the superposition of these functions on \({\mathcal {M}}\) mimics \(k = 8\) modes. The associated eigenfunctions are shown in Fig. 14c; again, there is excellent agreement between the analytic solution (i.e., \(\exp (-\imath ks)\)) and the EDMD computed solution.
a A sketch of the manifold \(s\mapsto (s, s)\) where our dynamical system is defined, and the larger domain, \(\Omega \), on which the elements of \({\mathcal {D}}\) are defined. b A plot of the leading 56 eigenvalues of \(\partial _s^2\) computed using EDMD; the redundant functions have increased the dimension of the nullspace from 1 to 50, but accurately capture the pairs of eigenvalues at \(-k^2\) for \(k=0,1,2,\ldots ,8\). c A plot of the real part of the first three non-trivial eigenfunctions shown in black, red, and blue respectively; as expected, they are equivalent to \(\cos (ks)\). The imaginary component of the eigenfunctions, which is not shown, captures the \(\sin (ks)\) terms (Color figure online)
The resulting eigenfunctions can also be evaluated for \((x,y)\not \in {\mathcal {M}}\), but the functions have no dynamical meaning there. Indeed, their value is determined entirely by the regularization used and has no relationship to the underlying dynamical system, which is defined solely on \({\mathcal {M}}\). This should be contrasted to related works such as Froyland et al. (2014) where the dynamical system is truly defined on \(\Omega \), and \({\mathcal {M}}\) is simply the slow manifold where the eigenfunctions evaluated at \((x,y)\not \in {\mathcal {M}}\) are meaningful as they contain information about the fast dynamics of the system.
Overall, the performance of the EDMD procedure is dependent upon the subspace, \({\mathcal {F}}_{{\mathcal {D}}}\) and not the precise choice of \({\mathcal {D}}\). There are numerical advantages of choosing \({\mathcal {D}}\) to be a basis for \({\mathcal {F}}_{{\mathcal {D}}}\), but in many circumstances this cannot be done without prior knowledge of \({\mathcal {M}}\). As a result, there are likely benefits to combining EDMD with manifold learning techniques [see, e.g., Coifman and Lafon (2006), Lee and Verleysen (2007), Erban et al. (2007) and Sirisup et al. (2005)]. These methods can numerically approximate \({\mathcal {M}}\), which could allow a more effective choice of the elements of \({\mathcal {D}}\) and their associated numerical benefits. As shown here, these methods are not essential to the algorithm, but \({\mathcal {M}}\) must be identified through some means if EDMD is to be used for more than just data analysis.
Rights and permissions
About this article
Cite this article
Williams, M.O., Kevrekidis, I.G. & Rowley, C.W. A Data–Driven Approximation of the Koopman Operator: Extending Dynamic Mode Decomposition. J Nonlinear Sci 25, 1307–1346 (2015). https://doi.org/10.1007/s00332-015-9258-5
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00332-015-9258-5