Finite-Data Error Bounds for Approximating the Koopman Operator: Sampling Measures, Super-Polynomial Convergence and Regularization

Abstract

The Koopman operator is a well-established framework for lifting nonlinear dynamical systems to an infinite-dimensional space where dynamics are linear. Extended Dynamic Mode Decomposition (EDMD) is a widely used method in data-driven dynamics as it provides a Galerkin approximation of the Koopman operator on the finite-dimensional span of a prescribed dictionary of observable functions. In particular, EDMD only requires samples from the dynamical system, describing the Koopman operator without knowledge of the underlying dynamics. While many studies analyze asymptotic convergence results for EDMD in terms of data, the question of more practical finite-data convergence results remains incomplete in general settings. In this work, we prove bounds for the finite-data EDMD Galerkin approximation of the Koopman operator by a rate proportional to the inverse of the root of the number of samples (the Monte Carlo rate). These results apply to multiple classes of problems, i.e., for discrete or continuous dynamics, including stochastic systems. In certain more structured setting, we demonstrate super-polynomial rates are achievable both theoretically and computationally. Finally, we derive recovery guarantees for an EDMD variant in the undersampled regime inspired by compressed sensing techniques.