On the Approximation of Koopman Spectra for Measure Preserving Transformations

Nithin Govindarajan, Ryan Mohr, Shivkumar Chandrasekaran, Igor MezicSIAM J. Appl. Dyn. Syst 2019 · DOI

TL;DR

This paper introduces a novel numerical method to approximate the spectral properties of Koopman operators for measure-preserving dynamical systems. By leveraging "periodic approximations" and permutation operators, the authors provide a way to compute spectral projections and density functions, offering a powerful tool for analyzing complex dynamics and developing reduced-order models.

What Problem Does This Paper Address?

Understanding the long-term behavior and statistical properties of dynamical systems is crucial in many scientific fields. The Koopman operator, a linear operator acting on observables of a dynamical system, provides a powerful framework for this analysis. Its spectral properties, particularly its spectrum, reveal fundamental information about the system's dynamics, such as periodicity and chaotic behavior. However, computing these spectral properties for continuous, measure-preserving transformations on compact spaces is notoriously challenging. Existing methods often struggle with continuous spectra or require strong assumptions. This paper aims to bridge this gap by developing a robust numerical method that can approximate the Koopman operator's spectrum, even for systems with continuous or mixed spectral components.

Methods

The core of the paper lies in a novel discretization strategy for the Koopman operator. Instead of directly approximating the operator, the authors propose constructing a sequence of finite-dimensional permutation operators that periodically approximate the underlying measure-preserving transformation. This "periodic approximation" involves partitioning the state space into equal-measure cells and defining a discrete map that permutes these cells.

Key methodological contributions include:

  • Periodic Approximation: A rigorous construction of bijective maps ($T_n$) that approximate the original transformation ($T$) in a Hausdorff metric sense. This is achieved by solving a bipartite matching problem.
  • Permutation Operators: The discrete Koopman operators derived from these periodic approximations are shown to be isomorphic to permutation operators. This structure simplifies spectral analysis significantly, as permutation operators have pure point spectra (eigenvalues are roots of unity).
  • Spectral Convergence: The paper establishes theoretical results showing that the spectral measure and spectral projectors of these discrete operators converge weakly to their infinite-dimensional counterparts.
  • Numerical Implementation: The authors detail an efficient algorithm for computing spectral projections and density functions using the discrete Fourier transform (DFT) and exploiting the cyclic decomposition of permutation matrices.

Datasets

Not discussed in the paper. The paper focuses on theoretical development and numerical illustration using canonical examples of dynamical systems.

Key Insights and Ideas

  • Permutation Operators as Natural Approximators: The paper highlights that permutation operators, being unitary and preserving certain properties of the Koopman operator (like positivity and invariant constant functions), are a natural choice for discretization.
  • Weak Convergence is Sufficient: The authors emphasize that while strong convergence of spectral projectors might be elusive, weak convergence of spectral measures and projectors on specific subspaces is achievable and sufficient for practical analysis and model reduction.
  • Handling Continuous Spectra: The proposed method's strength lies in its ability to handle systems with continuous spectra, which are often problematic for other techniques. The discretization effectively "resolves" the continuous spectrum into a dense set of discrete eigenvalues.
  • Algorithmic Efficiency: By leveraging the structure of permutation matrices and the DFT, the authors develop computationally efficient algorithms for spectral analysis.

Key Results

  • Theoretical Guarantees: The paper provides theoretical proofs for the weak convergence of spectral measures and projectors of the discretized Koopman operator to the true operator's spectral properties.
  • Numerical Method: A constructive and convergent numerical method is presented for computing spectral projections and density functions for volume-preserving maps on the m-torus.
  • Computational Complexity: The method's complexity is analyzed, showing it can be efficient, particularly for Lipschitz continuous maps, with a complexity often dominated by DFT computations (e.g., $O(\tilde{n}^m \log \tilde{n})$).
  • Illustrative Examples: The method is successfully applied to canonical examples:
  • Translation on the torus: Demonstrates a fully discrete spectrum.
  • Arnold's cat map: Exhibits a fully continuous spectrum.
  • Anzai's skew-product transformation: Shows a mixed spectrum.
  • Chirikov standard map: Analyzes a system with chaotic behavior, revealing how continuous spectra can break down into discrete components under perturbation.

Limitations and Future Work

  • Generalization to Non-Lebesgue Measures: A significant open question is how to generalize the method to systems with invariant measures that are not absolutely continuous with respect to the Lebesgue measure (e.g., measures on fractal attractors).
  • Convergence Rates: Deriving explicit convergence rate results for the current algorithm is suggested as future work.
  • Dissipative Systems: Extending the approach to dissipative systems, where periodic approximations might be replaced by many-to-one maps, is another promising direction.
  • Flows: Generalizing the procedure to handle continuous-time flows is also planned for a future publication.
  • Smoothness Conditions: The convergence of spectral projectors relies on certain smoothness conditions, and the paper notes that this can be a limitation if discrete spectra occur at the boundaries of the interval of interest.

Summary updated

BibTeX
@article{govindarajan2019approximation,
  author = {Nithin Govindarajan and Ryan Mohr and Shivkumar Chandrasekaran and Igor Mezic},
  title = {{On the Approximation of Koopman Spectra for Measure Preserving Transformations}},
  journal = {SIAM J. Appl. Dyn. Syst},
  year = {2019},
  doi = {10.1137/18m1175094},
}
Figure