On the Koopman operator of algorithms

DOI10.1137/19M1277059zbMATH Open1437.47048arXiv1907.10807MaRDI QIDQ5109369FDOQ5109369

I. G. Kevrekidis, Thomas N. Thiem, Felix Dietrich

Publication date: 11 May 2020

Published in: SIAM Journal on Applied Dynamical Systems (Search for Journal in Brave)

Abstract: A systematic mathematical framework for the study of numerical algorithms would allow comparisons, facilitate conjugacy arguments, as well as enable the discovery of improved, accelerated, data-driven algorithms. Over the course of the last century, the Koopman operator has provided a mathematical framework for the study of dynamical systems, which facilitates conjugacy arguments and can provide efficient reduced descriptions. More recently, numerical approximations of the operator have enabled the analysis of a large number of deterministic and stochastic dynamical systems in a completely data-driven, essentially equation-free pipeline. Discrete or continuous time numerical algorithms (integrators, nonlinear equation solvers, optimization algorithms) are themselves dynamical systems. In this paper, we use this insight to leverage the Koopman operator framework in the data-driven study of such algorithms and discuss benefits for analysis and acceleration of numerical computation. For algorithms acting on high-dimensional spaces by quickly contracting them towards low-dimensional manifolds, we demonstrate how basis functions adapted to the data help to construct efficient reduced representations of the operator. Our illustrative examples include the gradient descent and Nesterov optimization algorithms, as well as the Newton-Raphson algorithm.

Full work available at URL: https://arxiv.org/abs/1907.10807

Recommendations

• Applied Koopmanism
• A data-driven approximation of the koopman operator: extending dynamic mode decomposition
• Two methods to approximate the Koopman operator with a reservoir computer
• Koopman operator, geometry, and learning of dynamical systems
• The mpEDMD Algorithm for Data-Driven Computations of Measure-Preserving Dynamical Systems

zbMATH Keywords

Newton-Raphson methodKoopman operatorextended dynamic mode decompositionNesterov methodgradient descent optimizationEDMD algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Functional analytic techniques in dynamical systems; zeta functions, (Ruelle-Frobenius) transfer operators, etc. (37C30) Applications of operator theory in optimization, convex analysis, mathematical programming, economics (47N10) One-parameter semigroups and linear evolution equations (47D06) Numerical solutions to abstract evolution equations (65J08)

Cites Work

• Title not available (Why is that?)
• Discovering governing equations from data by sparse identification of nonlinear dynamical systems
• Dynamic mode decomposition of numerical and experimental data
• Analysis of Fluid Flows via Spectral Properties of the Koopman Operator
• Title not available (Why is that?)
• A short course on operator semigroups
• Eine Spektraltheorie für allgemeine Operatoren eines unitären Raumes. Erhard Schmidt zum 75. Geburtstag in Verehrung gewidmet
• Zur Operatorenmethode in der klassischen Mechanik
• Dynamical systems that sort lists, diagonalize matrices, and solve linear programming problems
• Spectral properties of dynamical systems, model reduction and decompositions
• Applied Koopmanism
• A kernel-based method for data-driven Koopman spectral analysis
• A data-driven approximation of the koopman operator: extending dynamic mode decomposition
• Title not available (Why is that?)
• Study of dynamical systems from the viewpoint of complexity and computational capabilities
• Linear algebra algorithms as dynamical systems
• Nonparametric Uncertainty Quantification for Stochastic Gradient Flows
• A generalized eigenvalue algorithm for tridiagonal matrix pencils based on a nonautonomous discrete integrable system
• Differential Equations for Roaming Pseudospectra: Paths to Extremal Points and Boundary Tracking
• Towards tensor-based methods for the numerical approximation of the Perron-Frobenius and Koopman operator
• Solving equations through particle dynamics
• Data-driven model reduction and transfer operator approximation
• New algorithms for macromolecular simulation. Selected papers based on the presentation at 4th international symposium, Leicester, UK, August 18--21, 2004.
• Data-driven spectral analysis of the Koopman operator
• Data-driven spectral decomposition and forecasting of ergodic dynamical systems
• Isostables, isochrons, and Koopman spectrum for the action-angle representation of stable fixed point dynamics
• Extended dynamic mode decomposition with dictionary learning: A data-driven adaptive spectral decomposition of the Koopman operator
• On the equivalence between SOR-type methods for linear systems and the discrete gradient methods for gradient systems
• Koopman-Based Lifting Techniques for Nonlinear Systems Identification
• Title not available (Why is that?)
• Koopman Operator Family Spectrum for Nonautonomous Systems
• On Matching, and Even Rectifying, Dynamical Systems through Koopman Operator Eigenfunctions
• Global linearization and fiber bundle structure of invariant manifolds
• Short note: An integrable numerical algorithm for computing eigenvalues of a specially structured matrix.
• Title not available (Why is that?)

Cited In (11)

• Dynamical Systems Theory and Algorithms for NP-hard Problems
• Time-series forecasting using manifold learning, radial basis function interpolation, and geometric harmonics
• On the Approximability of Koopman-Based Operator Lyapunov Equations
• A Recursively Recurrent Neural Network (R2N2) Architecture for Learning Iterative Algorithms
• On Koopman mode decomposition and tensor component analysis
• Numerical methods to evaluate Koopman matrix from system equations*
• Neural dynamic mode decomposition for end-to-end modeling of nonlinear dynamics
• The sparse-grid-based adaptive spectral Koopman method
• Modern Koopman Theory for Dynamical Systems
• Data-driven control of agent-based models: an equation/variable-free machine learning approach
• Quantum process tomography of unitary maps from time-delayed measurements

This page was built for publication: On the Koopman operator of algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5109369)