Ergodic Theory, Dynamic Mode Decomposition, and Computation of Spectral Properties of the Koopman Operator

Hassan Arbabi, Igor MezicSIAM J. Appl. Dyn. Syst 2017 · DOI

TL;DR

This paper establishes the theoretical convergence of Dynamic Mode Decomposition (DMD) algorithms for approximating the spectral properties of the Koopman operator, a linear operator that governs the evolution of observables in dynamical systems. By leveraging ergodic theory and a novel Hankel-matrix formulation, the authors provide a rigorous framework for data-driven analysis of complex systems, bridging the gap between theoretical Koopman operator theory and practical numerical computation.

What Problem Does This Paper Address?

Understanding the long-term behavior of complex dynamical systems, especially those with high dimensionality or chaotic dynamics, is a significant challenge. Traditional methods often struggle with the nonlinearities inherent in these systems. The Koopman operator theory offers a powerful alternative by linearizing the dynamics of observables (functions of the system's state) rather than the state itself. This linearization allows for the use of linear system analysis tools to understand nonlinear systems. However, a major hurdle has been the lack of rigorous theoretical guarantees for numerical methods, like Dynamic Mode Decomposition (DMD), that aim to approximate the Koopman operator's spectral properties (eigenvalues and eigenfunctions) from observed data. This paper addresses this gap by providing a theoretical foundation for DMD's convergence for ergodic systems, which are common in many physical phenomena.

Methods

The authors introduce a novel approach that combines Hankel matrices with Dynamic Mode Decomposition (DMD).

  • Hankel Matrices: These matrices are constructed from time-series data of observables by embedding delayed versions of the data. This technique, known as delay-embedding, is a standard method for reconstructing the state space of a dynamical system from partial observations. The paper shows that Hankel matrices provide an ergodic sampling of the Krylov sequence of observables.
  • Dynamic Mode Decomposition (DMD): The paper analyzes three variants of DMD: companion-matrix DMD, SVD-enhanced DMD, and Exact DMD. The core idea of DMD is to approximate the Koopman operator by constructing a finite-dimensional matrix from data snapshots and then computing its eigenvalues and eigenvectors.
  • Ergodic Theory: The theoretical convergence proofs heavily rely on Birkhoff's ergodic theorem. This theorem connects time averages of observables along a trajectory to their spatial averages over the system's state space. This connection is crucial for showing that data-driven projections (vector projections) can approximate function projections in the space of observables.
  • Singular Value Decomposition (SVD) and Proper Orthogonal Decomposition (POD): The paper establishes a connection between SVD applied to data matrices and POD of observables. This allows them to construct an orthonormal basis for the space spanned by the observables, which is essential for representing the Koopman operator.

Datasets

The paper does not introduce new datasets. Instead, it uses well-known dynamical systems for numerical demonstrations:

  • Lorenz System: A classic example of a chaotic system used to demonstrate the representation of chaotic dynamics.
  • Periodic and Quasi-Periodic Cavity Flow: Used to showcase the computation of Koopman eigenvalues and eigenfunctions for systems exhibiting periodic and quasi-periodic behavior.
  • Van der Pol Oscillator: Employed to compute the asymptotic phase of trajectories, demonstrating the utility of Koopman eigenfunctions for understanding system behavior.

Key Insights and Ideas

  • Ergodic Theory as the Bridge: The paper's central insight is that ergodic theory provides the theoretical justification for why DMD, when applied to Hankel-embedded data, converges to the true Koopman operator spectral properties. Birkhoff's ergodic theorem allows data-driven inner products to approximate Hilbert space inner products.
  • Hankel Matrices as Ergodic Samplers: Hankel matrices, formed by delay-embedding time series, are shown to provide an effective way to sample the Krylov subspace of observables, which is directly related to the Koopman operator's action.
  • SVD as a Proxy for POD: The paper demonstrates that applying SVD to data matrices derived from ergodic sampling of observables yields an orthonormal basis that approximates the Proper Orthogonal Decomposition (POD) basis of the observables. This is a powerful connection for data-driven spectral analysis.
  • Lifting to Observable Space: The work highlights that analyzing dynamics in the space of observables, rather than just the state space, can offer a more robust representation, particularly for chaotic systems.

Key Results

  • Convergence Guarantees: The paper rigorously proves the convergence of companion-matrix Hankel-DMD for computing Koopman eigenvalues and eigenfunctions for ergodic systems. This means that as more data is collected, the computed spectral properties will approach the true values.
  • SVD-POD Connection: A formal connection is established between SVD on data matrices and POD of observables in the context of ergodic systems.
  • Numerical Validation: The theoretical results are demonstrated through numerical examples on chaotic, periodic, and quasi-periodic systems, showing good agreement with theoretical predictions and existing literature. For instance, in the periodic cavity flow example, computed frequencies and eigenfunctions show high accuracy with relative errors on the order of $10^{-5}$ and variance of eigenfunctions on the order of $10^{-6}$.

Limitations and Future Work

  • Ergodicity Assumption: The convergence proofs rely on the assumption that the dynamical system is ergodic. While many physical systems exhibit ergodic behavior, this is a limitation for non-ergodic systems.
  • Invariant Subspace Dimension: The convergence proofs for some methods assume knowledge of the dimension of the invariant subspace containing the observables. The paper suggests that this dimension can be approximated in practice by hard-thresholding singular values from the SVD.
  • Future Work: The authors suggest extending their work to non-ergodic systems and exploring the computation of dissipative eigenvalues (those inside the unit circle), which are relevant for understanding transient behavior and stability. They also mention the potential for using this framework for control purposes and analyzing chaotic dynamics.

Summary updated

BibTeX
@article{arbabi2017ergodic,
  author = {Hassan Arbabi and Igor Mezic},
  title = {{Ergodic Theory, Dynamic Mode Decomposition, and Computation of Spectral Properties of the Koopman Operator}},
  journal = {SIAM J. Appl. Dyn. Syst},
  year = {2017},
  doi = {10.1137/17m1125236},
}
Figure