PaperlayerView exact revision on arXiv

Source-linked AI summary

On the numerical approximation of the Perron-Frobenius and Koopman operator

Stefan Klus, Péter Koltai, Christof Schütte

arXiv:1512.05997v3math.DSmath.NA

TL;DR

The paper addresses how to numerically approximate the Perron–Frobenius and Koopman operators and clarify connections between their approaches. It reviews projection-based methods including Ulam’s method and EDMD, then illustrates them on stochastic differential equations and molecular-dynamics examples. The paper reports that EDMD accurately approximates smooth eigenfunctions with few basis functions, while its computational cost and basis dependence constrain its use.

  • Problem

    Connections between numerical approaches for approximating the adjoint Perron–Frobenius and Koopman operators have not been fully described.

  • Method

    The paper reviews projection-based finite-dimensional approximations, including Ulam’s method and EDMD, and compares methods developed for the two operators.

  • Results

    EDMD enables accurate approximation with a small number of basis functions when the Perron–Frobenius or Koopman eigenfunctions are smooth.

  • Takeaways & Limitations

    Methods developed for Koopman-operator approximation can also be used for the Perron–Frobenius operator, and vice versa.

  • Takeaways & Limitations

    EDMD becomes computationally expensive for large m because it requires the pseudoinverse of a k × m data matrix, and its results depend on the chosen basis functions.

Abstract

from arXiv · show

Information about the behavior of dynamical systems can often be obtained by analyzing the eigenvalues and corresponding eigenfunctions of linear operators associated with a dynamical system. Examples of such operators are the Perron-Frobenius and the Koopman operator. In this paper, we will review different methods that have been developed over the last decades to compute finite-dimensional approximations of these infinite-dimensional operators - e.g. Ulam's method and Extended Dynamic Mode Decomposition (EDMD) - and highlight the similarities and differences between these approaches. The results will be illustrated using simple stochastic differential equations and molecular dynamics examples.

1 Introduction

The paper reviews operator-based analysis of dynamical systems, focusing on numerical approximations of Perron–Frobenius and Koopman operators and their connections. It emphasizes that Perron–Frobenius approximation can use a small number of long simulations, while the captured dynamics depend strongly on the chosen initial conditions.

  • Perron–Frobenius and Koopman operators are adjoint in appropriately defined function spaces, but distinct numerical approximation methods have been developed for them.
  • Perron–Frobenius methods analyze global dynamics across fields but are typically limited to low-dimensional problems when using adaptive box discretizations.The cited toolbox example is GAIO.
  • Data-based Koopman methods extract global behavior, support lower-dimensional approximations and fast–slow decompositions, and can replicate complex dynamics with a small number of modes.
  • A small number of long simulations can approximate the Perron–Frobenius operator, making the approach potentially suitable for experiments with few initial conditions and long observation times.Whether the resulting operator captures full system dynamics depends strongly on the selected initial conditions.
  • The paper reviews generalized Galerkin methods, compares numerical approaches for both operators, and illustrates them with stochastic differential equations and molecular-dynamics applications.Its sections cover operator properties, finite-dimensional representations, method relationships, examples, and conclusions.

2 Transfer operators

The transfer-operator framework represents dynamical-system evolution through linear operators: Perron–Frobenius evolves densities, while Koopman evolves observables. Their eigenfunctions and eigenvalues characterize invariant behavior, transients, metastability, and—in linear systems—explicit observable dynamics.

  • Deterministic systems: For deterministic systems, a measurable map Φ evolves states through iterates, providing the basis for transfer-operator descriptions.The framework starts from a measure space and commonly considers discrete time, with continuous-time extensions.
  • Perron–Frobenius operator: The Perron–Frobenius operator maps an input density f to the density g of the transformed random variable Φ(x), and is linear, positive, non-expansive, and Markov.Under an invariant measure, it is well-defined and non-expansive on Lp(X) for every p in [1, ∞].
  • Nondeterministic systems: For nondeterministic systems, a transition density k specifies the distribution of Φ(x) and prevents concentration of substantial probability mass on measure-zero sets.
  • Spectral properties: Invariant densities satisfy Pf = f; subdominant eigenfunctions describe slowly converging transients and provide information about metastable sets.With additional assumptions, convergence can be geometric at a rate governed by the second dominant eigenvalue.
  • Koopman operator: The Koopman operator evolves observables by composing them with the dynamics, rather than evolving state-space densities.For nondeterministic systems, its definition uses an expectation to preserve duality with the Perron–Frobenius operator.
  • Koopman operator: The Koopman operator is the adjoint of the Perron–Frobenius operator under the L1–L∞ duality pairing, with L2 definitions available for specific choices of dynamics and measure.
  • Linear-system example: For a linear system, left eigenvectors of A generate Koopman eigenfunctions ϕi(x) = wi x with corresponding eigenvalues equal to the eigenvalues of A.Products of Koopman eigenfunctions are also eigenfunctions, with eigenvalues given by the products of the original eigenvalues.
  • Linear-system example: In the example, the first eight nontrivial Koopman eigenfunctions are illustrated, with left eigenvectors w1 = [0.8, −0.6] and w2 = 1/√5[2, 1], and eigenvalues 0.6 and 0.4.

3 Numerical approximation

The paper presents generalized Galerkin and related data-based methods for finite-dimensional approximation of Perron–Frobenius and Koopman operators. It connects Ulam’s method, higher-order discretizations, EDMD, and DMD while noting computational and structural trade-offs.

  • 3.1 Generalized Galerkin methods: Galerkin projection represents an operator on a finite-dimensional basis by matching projected inner products.When basis and test functions differ, Petrov–Galerkin projection uses the dual space; with more test than basis functions, least squares defines an over-determined variant.
  • 3.2 Ulam’s method: Ulam’s method projects the Perron–Frobenius operator onto piecewise-constant indicator functions of a box partition.Its matrix entries represent transition probabilities between boxes and can be estimated by Monte Carlo sampling of test points and their images.
  • 3.2 Ulam’s method: A row-stochastic Ulam matrix defines a finite Markov chain whose eigenvalue-1 left eigenvector approximates the invariant measure.Higher-order piecewise polynomial methods can improve operator and dominant-spectrum approximations, while sparse-grid, spectral, and radial-basis approaches target additional regularity or flexibility.
  • 3.3 Further discretization methods for the Perron–Frobenius operator: Optimization-based schemes using g log g objective functionals provide convergent methods for approximating invariant densities, but their basis functions can be nontrivial combinations of test functions and dynamics.This approach is motivated partly by restrictive available convergence analysis for Ulam’s method.
  • 3.4 Extended dynamic mode decomposition: EDMD approximates Koopman eigenfunctions by left eigenvectors and Koopman modes by right eigenvectors of its matrix representation.For polynomial basis functions in the reported example, EDMD matched theoretical eigenfunctions with numerical error ε < 10^-10; exact DMD is a special case of EDMD using linear basis functions.
  • 3.4 Extended dynamic mode decomposition: For large numbers of data snapshots, EDMD converges to a Galerkin approximation, but computing the pseudoinverse of the k × m data matrix can become computationally expensive.This establishes a direct connection between data-based EDMD and Galerkin discretization while identifying a scaling limitation.

4 Duality

The paper connects numerical approximations of the adjoint Perron–Frobenius and Koopman operators, focusing on how Ulam’s method and EDMD relate. EDMD can approximate Perron–Frobenius eigenfunctions with arbitrary basis functions, but the results depend strongly on basis representation and eigenvector-computation cost.

  • Computation of the dual basis: The adjoint eigenfunctions can be obtained from Koopman eigenfunctions, or vice versa, using the corresponding finite-dimensional eigenfunction representations.The construction normalizes the pairings of eigenfunctions of the two adjoint operators to δij.
  • Ulam’s method and EDMD: EDMD with indicator functions for a box discretization computes the same finite-dimensional operator representation as Ulam’s method.
  • Computation of the dual basis: Computing the dual basis requires all eigenvectors of the matrix MK, which may be prohibitively time-consuming for large dictionaries when only leading eigenfunctions are needed.The dual-basis coefficients use the inverse Gram matrix under the assumption that G is invertible.
  • EDMD for the Perron–Frobenius operator: Using monomials of order up to 10 and thin plate splines produces different invariant-density approximations, showing that EDMD depends strongly on the chosen basis.The example concerns a linear system whose expected invariant density is a Dirac distribution at the origin.
  • EDMD for the Perron–Frobenius operator: Basis adequacy can be assessed by adding basis functions and checking stability, or by computing a residual whose large value signals inaccurate eigenfunction representation.Adding many basis functions can deteriorate the condition number of the problem.
  • EDMD for the Perron–Frobenius operator: EDMD approximates Koopman eigenfunctions with left eigenvectors and Perron–Frobenius eigenfunctions with right eigenvectors of a generalized eigenvalue problem involving (A, G).This formulation permits arbitrary basis functions for approximating Perron–Frobenius eigenfunctions.

5 Numerical examples

The examples apply Ulam’s method and EDMD to stochastic systems and molecular dynamics, comparing operator eigenfunctions and their ability to reveal metastable behavior. Results include double- and triple-well systems and n-butane conformations.

  • Examples: The numerical examples illustrate projection-based approximations of Perron–Frobenius and Koopman operators using stochastic differential equations and molecular dynamics.The examples include double-well and triple-well potentials and the n-butane molecule.
  • Double-well problem: Ulam’s method uses 2500 parameters, whereas EDMD uses 66 monomial basis functions for the double-well experiment.The domain is partitioned into 50×50 boxes for Ulam’s method, while EDMD uses monomials through order 10.
  • Double-well problem: The double-well system has two metastable states, which the second Perron–Frobenius eigenfunction can detect.The corresponding adjoint Koopman eigenfunction is nearly constant within each metastable region and changes abruptly between them.
  • Triple-well problem: For the coupled triple-well potential, ϕ2 separates the two deep wells, while ϕ3 separates the deep wells from the shallow well.The eigenfunctions of both operators are compared for this nonseparable potential.
  • n-butane: In n-butane, the first spatial-transfer eigenfunction predicts high probabilities for gauche and anti conformations and low probabilities for the other configurations.The signs of the second and third eigenfunctions contain information about metastable sets.

6 Conclusion

The paper reviews projection-based methods for finite-dimensional Perron–Frobenius and Koopman approximations, emphasizing their similarities and differences. It concludes that EDMD can be accurate with few basis functions for smooth eigenfunctions, while tensor extensions remain an open direction.

  • Conclusion: The paper reviews Ulam’s method and EDMD as projection-based methods for finite-dimensional approximations of Perron–Frobenius and Koopman operators.It also compares their similarities and differences across several examples.
  • Conclusion: Methods developed for Koopman-operator approximation can also be used for Perron–Frobenius approximation, and vice versa.
  • Conclusion: When Perron–Frobenius or Koopman eigenfunctions are smooth, EDMD enables accurate approximation with a small number of basis functions.The paper therefore identifies EDMD as suitable for higher-dimensional problems in this setting.
  • Conclusion: Tensor-based extensions for these eigenvalue problems are a possible next step, but not all numerical methods needed for generalization are currently available.The proposed direction concerns reversible processes and may support analysis of high-dimensional systems.

A Adjoint EDMD

The adjoint EDMD appendix represents observables in a finite dictionary and organizes sampled input-output data through matrix-valued evaluations. Linear operators on the dictionary span are then identified with matrix representations.

  • Adjoint EDMD: The appendix uses a linearly independent, piecewise continuous dictionary D of basis functions ψ_i: R^d → R.
  • Adjoint EDMD: The function space V is the span of D, and coefficient vectors represent functions through linear combinations of the basis functions.
  • Adjoint EDMD: A linear operator on V is identified with its k×k matrix representation relative to the dictionary basis.The convention uses multiplication from the left.
  • Adjoint EDMD: Sample points are collected as columns of X and Y, while Ψ_X and Ψ_Y collect the corresponding vector-valued basis evaluations.

Scalar products.

The appendix constructs a weighted scalar-product matrix from dictionary functions and uses it to express adjoint operators in finite-dimensional coordinates. Equal-measure Ulam boxes yield an especially simple transpose representation.

  • Scalar products: The weighted L2 scalar products of dictionary elements are represented using integrals of products ψ_iψ_j against a positive measure μ.
  • Scalar products: The resulting matrix S is symmetric positive definite and therefore invertible.
  • Scalar products: The adjoint of a linear operator is obtained by reformulating its defining duality relation in the finite-dimensional basis coordinates.
  • Scalar products: When S is a multiple of the identity, the transpose matrix represents the adjoint; this includes Ulam’s method with equal-measure boxes.

The Perron–Frobenius operator.

The section develops finite-dimensional approximations of the Perron–Frobenius and Koopman operators through Galerkin-related constructions, including data-based EDMD. In the infinite-data limit, EDMD converges to a Galerkin approximation of the Koopman operator, while the same framework suggests an approximation of the Perron–Frobenius projection.

  • In the infinite-data limit, the data-based Koopman approximation converges to a Galerkin approximation on V with respect to ⟨·,·⟩µ.The data points are sampled according to µ.
  • With sufficient data, the same framework suggests approximating the Galerkin projection of the Perron–Frobenius operator Pµ onto V.The approximation uses the symmetric positive definite weight matrix S.
  • The Perron–Frobenius operator can be approximated using a measure ρ different from the empirical distribution µ of the data points.
  • The operator-theoretic considerations extend to non-deterministic dynamics.

B On the ergodic behavior of one-step pairs

This section constructs a one-step-pair dynamical system for a non-deterministic process and identifies its invariant density. Geometric ergodicity of the original process transfers to the pair system.

  • For a non-deterministic dynamical system with transition density k and unique invariant density f, the one-step-pair system has invariant density f(x)k(x,y).The pair system is defined on X × X.
  • The transition density of the pair system is kΨ((x,y),(u,z)) = δy(u)k(u,z).
  • The argument uses invariance of f under Φ and the definition of the Perron–Frobenius operator.
  • Geometric ergodicity of Φ with respect to f implies ergodicity of the pair dynamics Ψ with respect to f(x)k(x,y).

C EDMD for the reduced spatial transfer operator

The section defines a spatial transfer operator on reduced coordinates and relates molecular-dynamics EDMD to its Galerkin projection. In the infinite-data limit, EDMD converges to that projection in L2(U, µU).

  • A smooth mapping ξ: Q → U ⊂ R^r selects essential coordinates intended to describe metastable behavior.The mapping may be nonlinear; for n-butane, r = 1 and ξ maps configurations to the dihedral angle ϕ.
  • The reduced-coordinate map ξ is assumed to be physically relevant, such as a reaction coordinate.
  • The spatial transfer operator for ξ is defined on L2(U, µU), where dµU(z) = fU(z)dz.Its construction uses the coarea formula and the marginal canonical density.
  • Ergodicity of Langevin dynamics converts time-sampled molecular trajectories into the limiting inner-product relation used by EDMD.The trajectory consists of positional coordinates sampled at times t, and φ and ψ are basis functions on U.
  • In the infinite-data limit, EDMD converges to a Galerkin projection in L2(U, µU) of the spatial transfer operator for the essential coordinates.

D Derivation of the EDMD-discretized Koopman operator

This section derives EDMD as an over-determined Petrov–Galerkin method operating on dictionary evaluations at paired data points. The resulting matrix is obtained by least squares and can be viewed as DMD applied to transformed data.

  • EDMD represents the Koopman operator on the span of a finite dictionary D = {ψ1, …, ψk}.The coefficient vector is mapped by left multiplication with the matrix K.
  • EDMD is an over-determined Petrov–Galerkin method using initial data points xℓ and their dynamical images yℓ.
  • The data pairs impose ψ(yℓ) = K^Tψ(xℓ), which yields the matrix formulation using ΨX and ΨY.
  • The EDMD matrix solves a Frobenius-norm least-squares problem and is obtained using the pseudoinverse of ΨX.
  • EDMD can be interpreted as applying DMD to the transformed data matrices ΨX and ΨY.
Loading 1512.05997v3…