TL;DR
This paper provides rigorous mathematical guarantees for the convergence of Extended Dynamic Mode Decomposition (EDMD) to the Koopman operator, a powerful tool for analyzing nonlinear dynamical systems. The authors show that as the number of data samples and the dimension of the observable space increase, EDMD approximations not only converge to the true Koopman operator but also accurately predict system behavior over finite time horizons.
What Problem Does This Paper Address?
Analyzing high-dimensional nonlinear dynamical systems is a significant challenge. Traditional methods often struggle with the complexity and curse of dimensionality. The Koopman operator framework offers a linear perspective on nonlinear dynamics by lifting the state space to a space of observables where the dynamics become linear. However, applying this framework often requires approximating the infinite-dimensional Koopman operator. Extended Dynamic Mode Decomposition (EDMD) is a popular data-driven method for this approximation, but rigorous theoretical guarantees for its convergence and predictive accuracy, especially in the limit of infinite data and observables, were lacking. This paper aims to fill that gap by providing a comprehensive theoretical analysis of EDMD's convergence properties.
Methods
The paper builds upon existing work on EDMD, which approximates the Koopman operator by solving a least-squares problem based on sampled data. The core contributions are:
- Convergence of EDMD to the Koopman Projection: The authors prove that as the number of samples ($M$) goes to infinity, the EDMD operator ($K_{N,M}$) converges to $K_N$, which is the $L_2(\mu)$-orthogonal projection of the Koopman operator onto a finite-dimensional subspace of observables ($F_N$).
- Convergence of the Projection to the Koopman Operator: Crucially, they demonstrate that as the dimension of the observable subspace ($N$) goes to infinity, $K_N$ converges to the Koopman operator ($K$) in the strong operator topology. This implies that EDMD can, in principle, approximate the Koopman operator arbitrarily well.
- Spectral Convergence: The paper shows that accumulation points of the spectra of $K_N$ correspond to eigenvalues of $K$, and their associated eigenfunctions converge weakly.
- Finite-Horizon Prediction Convergence: A key practical implication is shown: predictions of future system states obtained using EDMD converge to the true future states in the $L_2(\mu)$ norm over any finite time horizon.
- Analytic EDMD: A by-product is an "analytic" version of EDMD that bypasses sampling if the system's transition map and the basis functions are known analytically, allowing direct computation of $K_N$.
- Convergence for $M=N$: The paper also analyzes the case where the number of samples equals the number of observables ($M=N$), showing convergence to weak eigenfunctions (or eigendistributions) of the Koopman operator.
Datasets
Not discussed in the paper. The analysis is theoretical and relies on the properties of dynamical systems and measures, rather than specific datasets. The paper does, however, use a numerical example of the logistic map for illustration.
Key Insights and Ideas
- Bridging the Gap: The paper rigorously connects the data-driven EDMD approximation to the theoretical Koopman operator, providing a solid mathematical foundation for its use.
- Infinite-Dimensional Limit is Key: The convergence of $K_N$ to $K$ as $N \to \infty$ is the critical step that allows EDMD to approximate the full Koopman operator, not just its projection onto a fixed subspace.
- Predictive Power: The convergence of finite-horizon predictions is a highly significant result for practical applications like forecasting and control, showing that EDMD can reliably predict system evolution.
- Spectral Information: The convergence of eigenvalues and eigenfunctions provides a way to extract meaningful spectral information about the underlying nonlinear dynamics.
- Analytic EDMD as a Tool: The analytic version offers a way to verify EDMD results or perform analysis when the system model is known, bypassing sampling errors.
Key Results
- Convergence of EDMD operator $K_{N,M}$ to $K_N$ as $M \to \infty$.
- Convergence of $K_N$ to the Koopman operator $K$ in the strong operator topology as $N \to \infty$.
- Convergence of finite-horizon predictions of observables in $L_2(\mu)$ norm.
- Accumulation points of $K_N$'s spectra correspond to $K$'s eigenvalues, with weak convergence of eigenfunctions.
- The paper provides an analytic method to compute $K_N$ directly.
Limitations and Future Work
- "With Probability One" Results: Many results are stated "with probability one," meaning they hold for almost all choices of sample points drawn from the distribution $\mu$.
- Non-zero Eigenfunction Limit: The spectral convergence results for eigenfunctions require that the weak limit of the eigenfunctions is non-zero.
- Practical Subspace Selection: The paper acknowledges that selecting the optimal finite-dimensional subspace of observables ($F_N$) is crucial for practical applications and suggests future work on non-asymptotic analysis for minimizing the error $||K_N - K||_{F_N}$ and ensuring $F_N$ contains relevant observables.
- Stochastic Systems: The paper mentions that similar analysis for stochastic systems has been investigated, suggesting this as a future direction.
- Analytic EDMD Applicability: While powerful, the analytic EDMD is limited to cases where the transition map and integrals are analytically tractable.
Summary updated