Source-linked AI summary
A Data-Driven Approximation of the Koopman Operator: Extending Dynamic Mode Decomposition
Matthew O. Williams, Ioannis G. Kevrekidis, Clarence W. Rowley
TL;DR
The paper addresses how to approximate Koopman spectral quantities for nonlinear systems without explicit governing equations. It introduces EDMD, which uses snapshot pairs and a dictionary of observables, and demonstrates accurate or useful eigenfunction-based results on deterministic and stochastic examples. The paper also identifies dictionary selection and redundancy as important limitations affecting the method.
Problem
Approximating Koopman eigenvalues, eigenfunctions, and modes is useful for linear descriptions of nonlinear dynamics but is nontrivial without knowledge of the underlying dynamics or geometry.
Method
EDMD computes a finite-dimensional least-squares approximation of the Koopman operator from snapshot pairs and a selected dictionary of observables, with regularization available through the pseudoinverse.
Results
Across four deterministic and stochastic examples, EDMD was highly accurate for a system with known eigenfunctions, useful for partitioning Duffing basins, and effective for dynamically meaningful Swiss Roll parameterization.
Takeaways & Limitations
EDMD can provide practical approximations of Koopman quantities and support nonlinear manifold parameterization and Koopman-based analysis without explicit governing equations.
Takeaways & Limitations
The best dictionary is an open question, and unknown domains can create redundant basis functions that require regularization and a pseudoinverse.
Abstract
from arXiv · showhide
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" [1]. 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.
1. Introduction.
The introduction motivates seeking linear descriptions of nonlinear dynamics through suitable observables and presents EDMD as a data-driven extension of DMD for approximating Koopman spectral quantities. It also frames EDMD’s application to deterministic and stochastic data and its potential uses in analysis and reduced-order modeling.
- Different state representations, including POD modes, Dynamic Modes, and Lagrangian particles, can summarize the same phenomenon.The choice of representation affects the resulting evolution description and computational convenience.
- Choosing sufficiently rich observables can produce an evolution law whose dynamics are governed by a linear operator and its spectrum.The Koopman operator provides this linear evolution on scalar observables, despite being infinite dimensional.
- Existing data-compatible approaches include GLA, the Ulam Galerkin method, and DMD, with different capabilities for approximating Koopman quantities.GLA can approximate modes and eigenfunctions but requires eigenvalues, while DMD has been used to analyze nonlinear fluid flows.
- EDMD approximates leading Koopman eigenfunctions, eigenvalues, and modes from snapshot pairs and a dictionary of scalar observables, extending DMD.The dictionary may contain polynomials, Fourier modes, spectral elements, or other functions of the full-state observable.
- With large data, EDMD’s eigenfunction approximation converges to a Galerkin approximation with residual orthogonal to the dictionary subspace.The manuscript also evaluates EDMD on deterministic and stochastic examples and considers applications such as nonlinear manifold parameterization.
- For Markov-process data, EDMD approximates eigenfunctions of the Kolmogorov backward equation, or stochastic Koopman operator.The manuscript applies the unchanged data-driven procedure to stochastic examples, including nonlinear manifold learning and model reduction.
2. Dynamic Mode Decomposition and the Koopman Operator.
The Koopman operator recasts nonlinear state evolution as linear evolution of scalar observables, while EDMD uses snapshot pairs and a chosen dictionary to approximate its spectral quantities. EDMD converges toward a Galerkin approximation under sampling and function-space assumptions, extends DMD through richer dictionaries, and reduces to DMD for a restrictive dictionary choice.
- 2.1. The Koopman Operator.: The Koopman operator is linear but infinite dimensional, acting on observables rather than states and defining a new dynamical system for their evolution.Its finite-dimensional truncation can provide a linear approximation of nonlinear dynamics without directly linearizing around a fixed point.
- 2.1. The Koopman Operator.: The full state observable g(x)=x links state and observable descriptions, allowing the state to be reconstructed by superimposing Koopman eigenfunctions weighted by Koopman modes.Each eigenfunction evolves according to its corresponding eigenvalue, replacing complex state evolution with straightforward linear evolution in observable coordinates.
- 2.2.1. Approximating the Koopman Operator and its Eigenfunctions.: EDMD approximates Koopman eigenvalues, eigenfunctions, and modes from successive snapshot pairs and a dictionary of scalar observables spanning a finite-dimensional subspace.The dictionary may contain polynomials, Fourier modes, spectral elements, or other functions of the full state observable.
- 2.2.1. Approximating the Koopman Operator and its Eigenfunctions.: EDMD determines its finite-dimensional operator through a least-squares problem, with truncated singular value decomposition available to regularize nonunique solutions.The resulting Koopman modes are obtained from the computed operator and the dictionary representation.
- 2.4. Relationship with DMD.: EDMD equals DMD only for a specific restrictive dictionary, whereas richer dictionaries retain additional expansion terms and may yield more useful Koopman eigenfunction approximations.DMD corresponds conceptually to using linear monomials, analogous to a one-term Taylor expansion; EDMD’s quality depends on dictionary choice.
3. The Choice of the Dictionary.
EDMD accuracy depends strongly on the dictionary of trial functions, whose choice must reflect the dynamical system, data distribution, domain, and sampling strategy. The paper discusses polynomial, radial-basis, and discontinuous spectral-element dictionaries, along with practical trade-offs in constructing them.
- EDMD accuracy and convergence depend on the trial functions spanning the observable subspace, with suitable choices including polynomials, Fourier modes, radial basis functions, and spectral elements.
- Unknown system domains complicate dictionary construction because enclosing all snapshots may introduce redundant basis functions and require pseudoinverse regularization.
- Hermite polynomials are broadly applicable on R^N when data are normally distributed and can approximate Koopman eigenfunctions through a Taylor-like expansion.
- Discontinuous spectral elements use Legendre polynomials on covering boxes, producing block-diagonal G matrices that remain easy to invert with many basis functions.
- Adaptive box subdivision balances basis span against quadrature accuracy by refining regions with many data points and pruning empty subdomains.
- Higher-order compactly supported Legendre functions can improve p-type convergence for smooth eigenfunctions, while thin plate splines offer mesh-free radial-basis alternatives for complex geometries.
- The optimal dictionary remains unknown, although polar-coordinate bases may better represent limit cycles and EDMD can still work with relatively naive choices.
4. Deterministic Data and the Koopman Eigenfunctions.
EDMD approximates Koopman eigenfunctions, eigenvalues, and modes from deterministic data, with accuracy depending on the chosen observable dictionary. In illustrative systems, it reproduces analytical results and supports basin identification and parameterization.
- Method: EDMD approximates Koopman eigenfunctions, eigenvalues, and modes from deterministic snapshot data using a chosen observable dictionary.The method is evaluated on systems with analytically known Koopman quantities and on the Duffing oscillator.
- Conclusion: The deterministic examples show that EDMD can remain useful with limited data, despite greater accuracy being possible with more data.The paper concludes that the method can approximate Koopman quantities and parameterize basins outside the large-data limit.
- Linear system results: 10 digits eigenvalue accuracy and a 10^-6 maximum pointwise eigenfunction difference were obtained for the linear test system.The first nine eigenfunctions were contained in the dictionary subspace, enabling close agreement with analytical results.
- Linear system results: Expanding the dictionary lets EDMD capture nonlinear Koopman eigenfunctions that standard DMD, with only linear terms, cannot reproduce.These additional eigenfunctions are unnecessary for the LTI example but can be needed for nonlinear systems.
- Approximation limits: Dictionary mismatch produces missing or erroneous eigenfunctions because the observable subspace may omit required terms or fail to be Koopman-invariant.Even with infinite data, the computation then corresponds to a projected operator rather than the full Koopman operator.
- Duffing oscillator: EDMD identified Duffing oscillator basins with a 0.5% classification error and used Koopman eigenfunction amplitude and phase to parameterize individual basins.The amplitude and phase form an action–angle-like coordinate system, although errors remain near basin edges.
5. Stochastic Data and the Kolmogorov Backward Equation.
EDMD extends to stochastic data without algorithmic changes, approximating eigenfunctions, eigenvalues, and modes associated with the stochastic Koopman operator. The section establishes this interpretation and validates it through theoretical convergence and stochastic examples.
- For Markov-process data, EDMD approximates eigenfunctions of the Kolmogorov backward equation, also called the stochastic Koopman operator.
- The stochastic analysis assumes data are generated by a Markov process, such as a stochastic differential equation.
- The method is shown to converge to a Galerkin method in the large-data limit.
- Finite-data accuracy is demonstrated using a one-dimensional stochastic differential equation with a double-well potential.
5.1. EDMD with Stochastic Data.
For stochastic systems, EDMD retains its algorithmic form while its outputs are interpreted through the stochastic Koopman operator and conditional expectations. Its accuracy depends on the dictionary, manifold, data, and generating dynamics.
- The stochastic Koopman operator maps an observable to its conditional expected value one timestep in the future.
- EDMD uses the same snapshot-sampling framework for stochastic data, with an additional expectation over the stochastic dynamics.
- The method’s accuracy depends on the dictionary, the manifold, the data, and the dynamics used to generate them.
- With indicator functions supported on boxes, EDMD is equivalent to the Ulam Galerkin method.
- In stochastic settings, Koopman modes reconstruct expected full-state observables rather than exactly specifying individual system states.
5.2. A Stochastic Differential Equation with a Double Well Potential.
A double-well stochastic differential equation tests EDMD against finite-difference approximations of the stochastic Koopman operator. The method agrees well for leading eigenvalues and eigenfunctions, while its accuracy depends on data volume, noise, and dictionary resolution.
- EDMD is evaluated on a one-dimensional stochastic differential equation with a double-well potential using finite-difference solutions as validation.
- The data comprise 10^6 initial points, evolved by Euler–Maruyama for Δt = 0.1, with a forty-degree-of-freedom discontinuous spectral-element dictionary.
- EDMD shows good agreement with directly computed eigenvalues and the leading nontrivial eigenfunction across different noise levels σ.
- Small-noise approximations of some eigenfunctions cannot be trusted near the unstable fixed point because they lack its singularity.
- As σ approaches zero, an eigenfunction can approach a delta function and leave the dictionary’s observable subspace, causing its tuple to disappear.
- M > 10^4 yields no visible leading-eigenvalue difference and leading-eigenfunction error below 10^-3.
- EDMD converges as M^-0.49, close to the predicted Monte Carlo rate O(M^-0.5).
5.3. Parameterizing Nonlinear Manifolds and Reducing Stochastic Dynamics.
EDMD can parameterize nonlinear stochastic manifolds using Koopman eigenfunctions and rank coordinates by dynamical timescale. On a Swiss Roll, the method recovers geometric coordinates and prioritizes slower directions under anisotropic diffusion.
- 5.3. Parameterizing Nonlinear Manifolds and Reducing Stochastic Dynamics: The Swiss Roll experiments use EDMD to obtain a data-driven manifold parameterization and reduce stochastic dynamics.
- 5.3.1. Parameterizing a Nonlinear Manifold with a Diffusion Process: For isotropic diffusion, the leading eigenfunctions are one-to-one with the Swiss Roll’s length and width coordinates.
- 5.3.1. Parameterizing a Nonlinear Manifold with a Diffusion Process: The experiment applies EDMD to three-dimensional transformed observations to recover a two-parameter description of the nonlinear manifold.
- 5.3.1. Parameterizing a Nonlinear Manifold with a Diffusion Process: EDMD computes eigenvalues −0.234 and −0.491 versus theoretical values −2/9 and −1/2, while still recovering a useful manifold parameterization.
- 5.3.2. Parameterizing a Nonlinear Manifold with Anisotropic Diffusion: Under anisotropic diffusion, EDMD ranks the slower width direction before the faster length direction.
- 5.3. Parameterizing Nonlinear Manifolds and Reducing Stochastic Dynamics: The leading eigenfunctions combine manifold geometry and dynamical information through eigenfunctions, modes, and eigenvalues.
6. Conclusions.
EDMD computes Koopman eigenvalues, eigenfunctions, and modes from snapshot pairs, with accuracy depending on sampling and dictionary selection. Examples show useful deterministic and stochastic applications, while manifold-defined dynamics constrain interpretation outside the manifold.
- Conclusions: EDMD computes Koopman eigenvalues, eigenfunctions, and modes from snapshot pairs by solving a finite-dimensional least-squares problem.With sufficient data, the approximation converges to a Galerkin method.
- Conclusions: Across four examples, EDMD handled deterministic and Markov-process data, producing accurate approximations and useful parameterizations or partitions.The examples included a linear system, Duffing oscillator, double-well SDE, and diffusion on a Swiss Roll.
- Conclusions: For diffusion on a nonlinear manifold, leading eigenfunctions provided a dynamically meaningful parameterization when the diffusion was anisotropic.The method captured dynamical structure rather than only geometric structure.
- Conclusions: In a redundant-dictionary example, EDMD accurately recovered eigenvalue pairs −k2 for k = 0, 1, 2, . . . , 8 despite a 50-dimensional nullspace.The pseudoinverse was critical for obtaining a unique solution when the matrix was singular.
- Conclusions: EDMD performance depends on the selected function subspace, sampling density, and dictionary, motivating possible combinations with manifold-learning techniques.Evaluations away from the manifold have no dynamical meaning when the system is defined solely on the manifold.