PaperlayerView exact revision on arXiv

Source-linked AI summary

Extended dynamic mode decomposition with dictionary learning: a data-driven adaptive spectral decomposition of the Koopman operator

Qianxiao Li, Felix Dietrich, Erik M. Bollt, Ioannis G. Kevrekidis

arXiv:1707.00225v1math.DS

TL;DR

EDMD requires a problem-dependent dictionary, which is difficult to choose for high-dimensional and highly nonlinear systems. The paper couples EDMD with a trainable neural-network dictionary and reports adaptive, accurate reconstructions using fewer dictionary terms than fixed-dictionary EDMD.

  • Problem

    Choosing an effective fixed EDMD dictionary is difficult for high-dimensional and highly nonlinear systems.

  • Method

    The paper combines EDMD with an iterative algorithm and a trainable artificial-neural-network dictionary adapted to data.

  • Results

    The adaptive algorithm achieves good reconstruction accuracy without choosing a fixed dictionary a priori and requires fewer dictionary terms than fixed-dictionary EDMD for a given accuracy.

  • Takeaways & Limitations

    Dictionary learning alleviates a central EDMD shortcoming and broadens the practical applicability of the Koopman framework.

Abstract

from arXiv · show

Numerical approximation methods for the Koopman operator have advanced considerably in the last few years. In particular, data-driven approaches such as dynamic mode decomposition (DMD) and its generalization, the extended-DMD (EDMD), are becoming increasingly popular in practical applications. The EDMD improves upon the classical DMD by the inclusion of a flexible choice of dictionary of observables that spans a finite dimensional subspace on which the Koopman operator can be approximated. This enhances the accuracy of the solution reconstruction and broadens the applicability of the Koopman formalism. Although the convergence of the EDMD has been established, applying the method in practice requires a careful choice of the observables to improve convergence with just a finite number of terms. This is especially difficult for high dimensional and highly nonlinear systems. In this paper, we employ ideas from machine learning to improve upon the EDMD method. We develop an iterative approximation algorithm which couples the EDMD with a trainable dictionary represented by an artificial neural network. Using the Duffing oscillator and the Kuramoto Sivashinsky PDE as examples, we show that our algorithm can effectively and efficiently adapt the trainable dictionary to the problem at hand to achieve good reconstruction accuracy without the need to choose a fixed dictionary a priori. Furthermore, to obtain a given accuracy we require fewer dictionary terms than EDMD with fixed dictionaries. This alleviates an important shortcoming of the EDMD algorithm and enhances the applicability of the Koopman framework to practical problems.

I. INTRODUCTION

The Koopman framework represents nonlinear dynamics through linear evolution of observables, enabling spectral analysis and applications to high-dimensional systems. EDMD makes this computationally tractable with finite dictionaries, but dictionary selection remains difficult; this paper introduces a trainable alternative.

  • The Koopman operator describes temporal observable evolution through linear, infinite-dimensional dynamics, even for nonlinear systems.
  • Koopman analysis supports spectral methods and focuses on fewer observables when the underlying system is high-dimensional.
  • EDMD approximates the Koopman operator as a finite-dimensional linear map on the span of a chosen dictionary, whose spectral properties approximate those of the operator.
  • EDMD improves performance over DMD by including observables beyond the system state.
  • The dictionary must be chosen a priori, and this choice strongly affects approximation quality, especially for high-dimensional and highly nonlinear systems.
  • The paper couples EDMD with an artificial-neural-network dictionary that adapts to data, demonstrated on the Duffing oscillator and Kuramoto-Sivashinsky PDE.

II. PRELIMINARIES

The Koopman operator acts on observables as a bounded linear operator, allowing nonlinear dynamical systems to be studied through spectral evolution and Koopman modes.

  • A discrete-time dynamical system evolves states according to x(n + 1) = f(x(n)) on a measurable space M.
  • Koopman analysis represents observables as functions on M, typically in the Hilbert space L2(M, ρ).
  • The Koopman operator K acts on observables by composition with the dynamics, Kφ = φ ◦ f.
  • Assuming suitable M and ρ makes K bounded, the operator becomes amenable to spectral analysis.
  • Koopman mode decomposition associates eigenfunctions and eigenvalues with modes of an observable, including the full-state observable O(x) = x.
  • For full-state observables, the decomposition provides a nonlinear counterpart to normal mode analysis.

B. Continuous-time systems

Continuous-time systems can be handled within the Koopman framework through infinitesimal generators or by sampling their flow maps. The resulting linear operator is theoretically tractable but difficult to compute spectrally because it is infinite-dimensional.

  • Continuous-time Koopman analysis can use infinitesimal generators or reinterpret the system discretely through its flow map.
  • Although Koopman dynamics are linear, computing their spectral properties is challenging because the operator is infinite-dimensional.
  • The section introduces EDMD and a machine-learning extension to address the need for selecting a fixed, potentially inefficient dictionary.

A. The EDMD algorithm

EDMD constructs a finite-dimensional Koopman approximation from dictionary observables and data, then extracts spectral information from the resulting matrix. Its finite-sample accuracy depends on approximate invariance and a judicious dictionary, motivating adaptive dictionary learning.

  • A. The EDMD algorithm: EDMD chooses dictionary functions Ψ and approximates the Koopman operator on their finite-dimensional span U(Ψ).
  • A. The EDMD algorithm: Data pairs are used to find a matrix K that minimizes the residual measuring how closely the dictionary subspace is preserved by the dynamics.
  • A. The EDMD algorithm: The computed matrix supports approximate Koopman eigenfunctions, eigenvalues, and modes for observables.
  • A. The EDMD algorithm: With increasing data, the EDMD matrix converges to the projected Koopman operator, while increasing dictionary size can yield strong operator convergence under stated conditions.
  • A. The EDMD algorithm: Finite-dimensional EDMD assumes approximate invariance of U(Ψ), which requires either many dictionary elements or a judiciously chosen dictionary.
  • A. The EDMD algorithm: Dictionary selection remains a central challenge because standard bases can be prohibitively expensive for highly nonlinear or high-dimensional systems.
  • A. The EDMD algorithm: The proposed machine-learning approach seeks high-quality representations with relatively fewer dictionary terms by optimizing the dictionary from data.

B. EDMD with Dictionary Learning (EDMD-DL)

EDMD-DL makes the EDMD dictionary trainable, adapting nonlinear basis elements to data to obtain an efficient finite-dimensional representation with smaller truncation error.

  • Dictionary learning adapts dictionary elements to data rather than fixing them in advance, targeting accurate and sparse representations.The formulation balances reconstruction residuals with regularization, while nonlinear dictionary functions require nonlinear optimization.
  • The sparse-coding objective uses a Frobenius reconstruction term and an ℓ1 penalty to promote sparsity without combinatorial ℓ0 optimization.Additional constraints such as normalized dictionary norms can remove degeneracies.
  • The trainable dictionary seeks an efficient representation with fewer adaptive basis elements and truncation errors analogous to sparse coding or KLD.The paper relates the approach to adaptive basis constructions whose goal is reduced truncation error.
  • EDMD-DL minimizes the residual Ψ∘f − KΨ by making the EDMD dictionary Ψ adaptive.This reframes the finite-dimensional Koopman projection as an optimization over both the operator approximation and dictionary.

C. A practical algorithm

The practical EDMD-DL algorithm parameterizes the dictionary with a neural network and alternates operator fitting with dictionary training until convergence.

  • EDMD-DL parameterizes Ψ(x; θ) with a universal function approximator, implemented as a feed-forward neural network.The network uses three hidden layers with affine transformations and tanh activations.
  • Fixed constant and coordinate-projection functions prevent the trivial zero dictionary and preserve the identity map needed for trajectory reconstruction.The projection maps allow the identity observable to lie in the span of the dictionary, enabling Koopman-mode reconstruction.
  • Each iteration fixes θ and optimizes K, then fixes K and updates θ by gradient descent.The K subproblem uses Tikhonov regularization, while the θ step is a standard machine-learning optimization without a closed-form solution.
  • When dimension and sample size are large, evaluating the gradient can be expensive, motivating stochastic gradient descent and its variants.
  • The alternating updates are iterated until convergence, and the resulting method is called EDMD with dictionary learning (EDMD-DL).The authors report stable empirical convergence for general initializations, while a rigorous convergence proof remains future work.

IV. APPLICATIONS OF EDMD-DL

The paper evaluates EDMD-DL against classical EDMD using trajectory-reconstruction and eigenfunction-approximation accuracy.

  • The applications compare EDMD-DL with classical EDMD using adaptive and fixed dictionary choices.
  • The first metric measures trajectory-reconstruction accuracy from the Koopman mode decomposition with the identity observable O(x) = x.
  • The second metric measures eigenfunction-approximation error for each eigenfunction indexed by j = 1, 2, . . . , M.

A. Duffing oscillator

For the Duffing oscillator, EDMD-DL achieves accurate trajectory and eigenfunction reconstruction with fewer adaptive dictionary elements than fixed EDMD dictionaries.

  • EDMD-DL outperforms both Hermite-polynomial and RBF EDMD in trajectory reconstruction despite the RBF dictionary being carefully selected for the Duffing equation.
  • EDMD-DL achieves lower reconstruction error at smaller dictionary sizes than EDMD with RBF dictionaries.The error comparison averages over 50 random initial conditions.
  • For leading eigenfunctions, EDMD-DL matches the well-chosen RBF dictionary and outperforms the poorly chosen Hermite dictionary.The comparison evaluates the first 8 leading eigenfunctions.
  • The Duffing experiment uses a flow-map time step of τ = 0.25 and evaluates reconstructions from initial conditions in [−2, 2]2.
  • With 25 dictionary elements, EDMD-DL reconstructs Duffing trajectories more accurately than Hermite-polynomial EDMD with the same dictionary size.
  • EDMD-DL performs approximately on par with EDMD using 100 RBF dictionary elements, despite using fewer trainable outputs.
  • The results indicate that dictionary learning is especially advantageous when choosing a dictionary systematically for high-dimensional systems is difficult.

B. Kuramoto-Sivashinsky PDE

For the Kuramoto-Sivashinsky PDE, EDMD-DL produces a richer and more meaningful Koopman spectrum and more accurate eigenfunction and trajectory reconstructions than fixed-dictionary EDMD, despite using fewer dictionary outputs.

  • Eigenvalues: Despite producing fewer eigenvalues, EDMD-DL yields a richer Koopman eigenvalue spectrum than the fixed-dictionary EDMD methods.The reported dictionary sizes are 101 for EDMD-DL, 250 for the state-and-derivatives dictionary, and 150 for the Fourier dictionary.
  • Eigenvalues: EDMD-DL produces more meaningful eigenvalues, whereas most eigenvalues from classical EDMD are effectively concentrated at 0.The PDE requires a richer representation; the fixed-dictionary methods produce inaccurate representations despite some eigenvalues having large magnitudes.
  • Trajectory reconstruction: EDMD-DL captures detailed trajectory behavior and reconstructs fine-scale solution structures that classical EDMD fails to reproduce.This comparison uses a reconstructed trajectory from a previously unseen initial condition.
  • Dictionary size and choice: EDMD-DL achieves good performance with smaller dictionary sizes, while adding Fourier modes does not improve the Fourier-basis method in this PDE case.The passage attributes this difficulty partly to the challenge of choosing a good dictionary for the Kuramoto-Sivashinsky PDE.
  • Eigenfunction errors: Dictionary learning yields much lower eigenfunction errors than classical EDMD and performs comparably to a well-chosen, larger RBF dictionary.The comparison uses 25 elements for EDMD-DL and Hermite EDMD, and 100 RBFs for RBF EDMD.

V. DISCUSSION

The discussion presents EDMD-DL as an adaptive alternative to fixed-dictionary EDMD, using machine learning to optimize observables for accurate Koopman approximations. Experiments show improved reconstruction and spectral approximation with fewer adapted dictionary functions, including for nonlinear and high-dimensional systems.

  • EDMD requires carefully chosen observables, and selecting effective dictionaries is difficult for highly nonlinear and high-dimensional systems.
  • EDMD-DL formulates dictionary selection as residual-norm optimization, allowing a small number of optimized functions to span an accurately approximated Koopman subspace.
  • The method combines EDMD with a neural-network function approximator and an iterative optimization algorithm.
  • EDMD-DL reconstructs fine-scale Kuramoto-Sivashinsky dynamics more accurately than classical EDMD with either tested dictionary.
  • Adaptive descriptions provide greater reconstruction accuracy over longer trajectories, including lengths exceeding those of the training trajectories.
  • Because EDMD-DL needs fewer dictionary elements, the authors identify applications to accurate reconstruction in high-dimensional ODE and PDE systems.

VI. CONCLUSION AND OUTLOOK

The conclusion frames EDMD-DL as a machine-learning-enhanced approach that addresses dictionary selection by optimizing the dictionary jointly with the finite-dimensional Koopman approximation. The authors connect this capability to broader applications while identifying convergence analysis and problem-specific variants as future directions.

  • The paper combines modern machine-learning approaches with EDMD to estimate spectral decompositions of the Koopman operator.
  • EDMD-DL treats the dictionary as an optimization variable and seeks the best finite-dimensional Koopman approximation for a specified dictionary size.
  • The resulting framework supports improved reconstruction and application of Koopman methods to a broader range of problems.
  • Future work includes studying conditions guaranteeing convergence of the iterative algorithm and exploring alternative regularization terms or function approximators.
  • The authors also propose investigating dictionary-element counts in relation to generic observables for systems evolving on low-dimensional manifolds.
  • They identify stochastic Koopman-related analysis as another possible extension of the method.
Loading 1707.00225v1…