PaperlayerView exact revision on arXiv

Source-linked AI summary

On Convergence of Extended Dynamic Mode Decomposition to the Koopman Operator

Milan Korda, Igor Mezić

arXiv:1703.04680v4math.OCmath.DSmath.SP

TL;DR

The paper addresses how EDMD approximations converge beyond the sampling limit and whether their predictions and spectral information approach those of the Koopman operator. It proves strong operator convergence as the observable dimension grows, establishes finite-horizon prediction and weak spectral results, and analyzes analytic and M=N variants under stated assumptions.

  • Problem

    Prior work established convergence of K_N,M to the finite-dimensional projection K_N as M →∞, leaving convergence of K_N toward the Koopman operator and related spectral behavior to analyze.

  • Method

    The paper analyzes EDMD limits as N increases, studies finite-horizon predictions and weak spectral convergence, proposes an analytic construction, and treats the special case M=N.

  • Results

    As N →∞, K_N converges strongly to the Koopman operator; finite-horizon predictions converge in L2(μ), and nonzero weak eigenfunction limits identify Koopman eigenvalues.

  • Takeaways & Limitations

    The results support asymptotically exact finite-horizon forecasting from EDMD and provide weak spectral information without assuming Koopman-invariant finite-dimensional observable subspaces.

  • Takeaways & Limitations

    Weak spectral convergence is obtained only along a subsequence when the weak eigenfunction limit is nonzero, and future work is needed on non-asymptotic subspace selection.

Abstract

from arXiv · show

Extended Dynamic Mode Decomposition (EDMD) 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 $μ$, it was shown that, in the limit as $M\rightarrow\infty$, the EDMD operator $\mathcal{K}_{N,M}$ converges to $\mathcal{K}_N$, where $\mathcal{K}_N$ is the $L_2(μ)$-orthogonal projection of the action of the Koopman operator on the finite-dimensional subspace of observables. In this work, we show that, as $N \rightarrow \infty$, the operator $\mathcal{K}_N$ 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$ 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 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$ directly, without the use of sampling. Finally, under additional assumptions, we analyze convergence of $\mathcal{K}_{N,N}$ (i.e., $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.

1 Introduction

The paper studies convergence of EDMD approximations to the Koopman operator, extending prior sampling-limit results to increasing observable dimension and several spectral and prediction consequences.

  • EDMD approximates Koopman dynamics through spectral methods used in model reduction, identification, prediction, data assimilation, and control.
  • As M →∞, the sampled EDMD operator K_N,M converges to the L2(μ)-orthogonal projection K_N under iid or ergodic sampling.
  • As N →∞, K_N converges to the Koopman operator in the strong operator topology, yielding finite-horizon prediction convergence in L2(μ).
  • Accumulation points of the spectra of K_N correspond to Koopman eigenvalues, with associated eigenfunctions converging weakly when their weak limit is nonzero.
  • An analytic EDMD variant constructs K_N without sampling when the transition map and required integrals are available in closed form.
  • The paper also analyzes the M=N case, proving subsequential convergence to weak eigenfunctions or eigendistributions related to Perron-Frobenius eigenmeasures.

2 Extended Dynamic Mode Decomposition

EDMD constructs a finite-dimensional Koopman approximation from snapshot pairs generated by a discrete-time dynamical system and selected observable basis functions.

  • The dynamical system is represented by a map T on a topological state space, with snapshot pairs satisfying y_i = T(x_i).
  • The framework permits arbitrary topological spaces, including finite-dimensional manifolds and infinite-dimensional systems from partial differential equations or control.
  • The Koopman operator acts on observables by composition with T, mapping ψ to ψ ◦ T.
  • Given N linearly independent basis functions, EDMD defines the observable subspace F_N and approximates Koopman dynamics there.
  • The EDMD operator K_N,M is obtained by solving a least-squares problem using the basis evaluations on the X and Y snapshot matrices.

3 EDMD as L2 projection

EDMD is characterized as an orthogonal projection of Koopman evolution onto the chosen observable subspace, with empirical and population measures defining the projection.

  • The Moore–Penrose construction provides a uniquely defined EDMD solution that remains a minimizer of the least-squares problem.
  • The empirical measure μ̂_M is built from the sampled points, while F_N is a closed subspace of both L2(μ̂_M) and L2(μ).
  • The Koopman restriction K|F_N maps the finite-dimensional observable subspace into the ambient observable space, without requiring F_N to be invariant.
  • When the empirical Gram matrix is invertible, the projection problem has a unique solution; otherwise, multiple L2(μ) minimizers may exist.
  • For φ ∈ F_N, K_N,Mφ is the L2(μ̂_M)-orthogonal projection of Kφ onto the span of the basis functions.

4 Convergence of KN,M as M →∞

With increasing sample count, EDMD converges to the finite-dimensional L2(μ)-projection under independence or ergodicity assumptions, including operator-norm and spectral convergence for fixed N.

  • The sample-limit analysis establishes convergence of K_N,M to K_N as M →∞, reducing convergence to Koopman dynamics to the behavior of K_N as N increases.
  • For iid sampling, basis-function independence under μ ensures the empirical Gram matrix is invertible with probability one when M ≥ N.
  • The strong law of large numbers yields convergence of empirical quantities and, consequently, K_N,Mφ → K_Nφ for every φ ∈ F_N.
  • Because the operators act on a finite-dimensional space, pointwise convergence implies operator-norm convergence and spectral convergence for fixed N.
  • The same conclusions hold for ergodic trajectory samples, with probability interpreted through the initial condition drawn from μ.

5 Convergence of KN to K

The paper extends EDMD convergence from finite-dimensional projections to increasing observable subspaces, proving strong operator convergence to the Koopman operator and weak spectral convergence under a nonzero-limit condition.

  • Operator extension: The analysis extends K_N from F_N to F by studying K_NP_N^μ, whose strong convergence can be compared directly with K.Precomposition with P_N^μ adds a zero to the spectrum but enables convergence analysis on the full space F.
  • Strong operator convergence: Strong operator convergence does not generally imply operator-norm or spectral convergence when the observable subspaces are not invariant.The paper therefore establishes spectral convergence only in a weak, subsequential sense.
  • Weak spectral convergence: Accumulation points of eigenvalues of K_N correspond to Koopman eigenvalues when normalized eigenfunctions converge weakly to a nonzero limit.The associated weak limit φ satisfies Kφ = λφ; if φ is nonzero, λ is an eigenvalue of K.
  • Weak spectral convergence: The nonzero weak-limit condition is necessary: highly oscillatory normalized functions can otherwise suggest spurious spectral accumulation despite converging weakly to zero.For the identity Koopman operator on [0,1], the true spectrum is {1}, while the example illustrates why vanishing weak limits require caution.

6 Implications for finite-horizon predictions

Strong convergence of the EDMD approximation yields asymptotically exact finite-horizon predictions in L2(μ), including predictions of vector observables and future states.

  • Finite-horizon convergence: For any finite prediction horizon Ω, iterates of the projected EDMD operator converge to the corresponding Koopman iterates in L2(μ).The result applies to a given vector observable f and follows by induction over the prediction horizon.
  • Practical predictor: When f is represented in the EDMD basis, its prediction is computed from the lifted observables using a coefficient matrix and powers of the EDMD matrix.If f = C_Nψ_N, the predicted value at T^i(x_0) is formed from C_N, A_N^i, and ψ_N(x_0).
  • Practical predictor: For future-state prediction, setting f(x)=x produces a predictor linear in the lifted state z=ψ_N(x), enabling linear tools for nonlinear dynamics.The paper connects this structure to applications in model predictive control and state estimation.
  • Finite-horizon convergence: The same finite-horizon convergence holds for K_N,M under a double limit that first sends M to infinity and then N to infinity.This transfers the projection result to the sampled EDMD operator after its established convergence to K_N.

7 Analytic EDMD

Analytic EDMD constructs K_N directly from analytically computable integrals, avoiding the sampling step of EDMD. The paper gives conditions for this construction and illustrates its spectral and predictive behavior against sampled EDMD.

  • Analytic construction: Polynomial or trigonometric maps and basis functions with simple measures such as uniform distributions on boxes or balls satisfy the stated analytic-evaluation setting.Gaussian measures on R^n are also given as an example.
  • Analytic construction: Analytic EDMD avoids sampling by constructing K_N directly when the required integrals can be evaluated analytically.This requires a known closed-form mapping T and basis functions ψ_i for which the relevant integrals are computable.
  • Analytic construction: When M_μ is invertible, the analytic operator construction is characterized by the unique minimizer of the associated projection problem.The invertibility condition makes M_μ Hermitian positive definite and the minimized function strictly convex.
  • Example: The logistic-map example uses degree-eight polynomials with a Laguerre basis orthonormal under the uniform measure on [−1, 1].The measure is not invariant, so the dynamics is not measure preserving.
  • Example: The example compares analytic K_N with sampled K_N,M across M values, showing that accurate spectral approximation requires relatively many samples.Figure 2 displays spectra for M = 10^2, 10^3, and 10^5.
  • Example: The same example compares predictions generated by K_N and K_N,M for different sample counts.Figure 3 presents the prediction comparison.

8 Convergence of KN,N

When the number of samples equals the number of observables, EDMD eigenvalues and eigenfunctions converge along subsequences under trajectory and homeomorphism assumptions, linking Koopman weak eigenfunctions to Perron–Frobenius eigenmeasures.

  • Under compactness, continuity, bounded eigenvalues, and single-trajectory sampling, normalized eigenmeasures admit a weakly convergent subsequence.
  • For M=N, the EDMD least-squares minimum is zero, so KN,N matches Koopman action on all sample points for every f in FN.
  • The limiting sampling measure is invariant under T, while the limiting functional is represented by a complex-valued measure through the Riesz representation theorem.
  • If the weak limit is nonzero, it is a weak eigenfunction or eigendistribution of the Koopman operator associated with the limiting eigenvalue.
  • If the limiting eigenvalue is nonzero, the limiting measure is an eigenmeasure of the Perron–Frobenius operator with eigenvalue 1/λ.

9 Conclusions

The paper establishes convergence of EDMD projections and finite-horizon predictions, derives weak spectral convergence, and analyzes the equal-sample case, while identifying non-asymptotic subspace selection as future work.

  • As M→∞, KN,M converges to the Koopman action projected onto the observable span, while KN converges strongly to the Koopman operator as N→∞.
  • Finite-horizon predictions converge in L2 norm, supporting applications including forecasting, estimation, and control.
  • Accumulation points of KN spectra corresponding to nonzero weak eigenfunction limits belong to the point spectrum of the Koopman operator.
  • For KN,N with trajectory sampling, convergence occurs along a subsequence to weak Koopman eigenfunctions or eigendistributions and related Perron–Frobenius eigenmeasures.
  • Future work should address non-asymptotic analysis and select subspaces that approximate K well while containing observables of practical interest.
Loading 1703.04680v4…