Sparse Online Koopman Learning Cuts Memory 75% on Streaming Trajectory Data
A new algorithm learns Koopman operators from streaming trajectory data with provable convergence and controlled model complexity, no batches required.
PRO- Sparse online algorithm learns Koopman operators iteratively from single trajectories via stochastic operator gradient descent.
- Handles mis-specified setting where the RKHS is not closed under the dynamics, a common real-world case.
- Establishes CME operator as the adjoint of Koopman in this mis-specified setting, unifying two learning problems.
- Provides both almost-sure asymptotic and finite-time mean-square convergence guarantees under Markovian sampling.
- Online kernel matching pursuit keeps dictionary tiny: 145 points from 40000 samples on Langevin dynamics.
- On OpenAI Gym pendulum, achieves 25% dataset reduction while approaching dynamic programming reference performance.
Analyzing nonlinear dynamical systems from data is a foundational problem across physics, control, and reinforcement learning. One popular workaround for the nonlinearity is the Koopman operator, which lifts a nonlinear system into an infinite-dimensional but linear operator acting on functions of the state. Once you have that linear representation, you can apply spectral tools, eigenfunctions, and mode decompositions to understand behaviors like stable regions and metastable sets. A new paper, Nonparametric Sparse Online Learning of the Koopman Operator, shows how to learn this operator from a single stream of trajectory samples rather than from a batch collected up front.
Why batch learning falls short
Existing sample-complexity analyses for Koopman and conditional mean embedding operators rely on writing them in terms of covariance operators, which are expectations of rank-one tensors, and then replacing said expectations with empirical means. That approach requires a fixed dataset of independent, identically distributed samples, but in practice you often only have a single ongoing trajectory from a Markov process, where consecutive samples are neither independent nor identically distributed.
A second obstacle is more subtle. Most kernel-based approaches assume the chosen function space is closed under the dynamics, meaning applying the operator to a function keeps you inside the space. This closedness assumption is restrictive and hard to verify. The authors give a simple illustration: pick a linear kernel with dynamics x_next = x^2
This story is for Pro members
You've reached the end of the free preview. Upgrade to AlphaSignal Pro to read the full article - and everything else behind the paywall.
Comments
