On the Koopman operator of algorithms

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.

arXiv comment27 pages, 11 figures

References in corpus (12)

• Discovering governing equations from data: Sparse identification of nonlinear dynamical systems
• A Data-Driven Approximation of the Koopman Operator: Extending Dynamic Mode Decomposition
• Applied Koopmanism
• A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights
• Extended dynamic mode decomposition with dictionary learning: a data-driven adaptive spectral decomposition of the Koopman operator
• Data-driven model reduction and transfer operator approximation
• Isostables, isochrons, and Koopman spectrum for the action-angle representation of stable fixed point dynamics
• Data Fusion via Intrinsic Dynamic Variables: An Application of Data-Driven Koopman Spectral Analysis
• Global linearization and fiber bundle structure of invariant manifolds
• Towards tensor-based methods for the numerical approximation of the Perron-Frobenius and Koopman operator
• On the equivalence between SOR-type methods for linear systems and discrete gradient methods for gradient systems
• A generalized eigenvalue algorithm for tridiagonal matrix pencils based on a nonautonomous discrete integrable system

Cited by in corpus (12)

• Physics-Informed Deep Learning For Traffic State Estimation: A Survey and the Outlook
• Time Series Forecasting Using Manifold Learning
• Data-driven Control of Agent-based Models: an Equation/Variable-free Machine Learning Approach
• Data-driven modelling of brain activity using neural networks, Diffusion Maps, and the Koopman operator
• Applications of Koopman Mode Analysis to Neural Networks
• Modeling Partially Observed Nonlinear Dynamical Systems and Efficient Data Assimilation via Discrete-Time Conditional Gaussian Koopman Network
• Generic Properties of Koopman Eigenfunctions for Stable Fixed Points and Periodic Orbits
• On Koopman Mode Decomposition and Tensor Component Analysis
• Quantum Process Tomography of Unitary Maps from Time-Delayed Measurements
• Numerical methods to evaluate Koopman matrix from system equations
• On the Correspondence between Gaussian Processes and Geometric Harmonics
• Error Estimation and Correction from within Neural Network Differential Equation Solvers