🤖 machine learning

Dictionary learning for Kernel EDMD

This paper proposes a dictionary learning approach for Kernel Extended Dynamic Mode Decomposition (kEDMD) that utilizes gradient-based optimization to automatically learn and prune kernel parameters from a weighted list, thereby streamlining the approximation of the Koopman operator for nonlinear dynamical systems.

Original authors: Erik Lien Bolager, Boumediene Hamzi, Houman Owhadi, Ioannis G. Kevrekidis, Felix Dietrich

Published 2026-04-29

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Erik Lien Bolager, Boumediene Hamzi, Houman Owhadi, Ioannis G. Kevrekidis, Felix Dietrich

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to predict the weather. The atmosphere is a chaotic, swirling mess of nonlinear forces. Trying to track every single air molecule is impossible. However, there is a mathematical trick called the Koopman operator that lets us look at this chaos through a different lens. Instead of watching the messy air molecules, we watch "observables" (like temperature or pressure) evolve in a way that is perfectly linear and predictable. It's like turning a tangled ball of yarn into a straight, smooth rope.

The problem is, to use this trick, we need to know exactly which "observables" to watch. In the past, scientists had to guess these manually, like trying to find the right key for a lock by testing every key in a giant ring. This is slow and often fails.

This paper introduces a new method called Dictionary Learning for Kernel EDMD. Think of it as teaching a computer to invent its own keys to unlock the system's behavior, rather than just trying the ones we already have.

Here is how the paper breaks it down, using simple analogies:

1. The Old Way: The "Fixed Dictionary" Problem

Traditionally, to study these systems, scientists use a method called EDMD. They create a "dictionary" of functions (like a list of ingredients) and feed data into it to see how the system evolves.

The Problem: If the system is complex, you need a massive dictionary. If the dictionary is too big, the math becomes too heavy for computers. If it's too small, you miss important details.
The Kernel Trick: To solve the "too big" problem, scientists started using Kernels. Instead of listing ingredients, they use a mathematical "recipe" (a kernel) that implicitly creates an infinite list of ingredients. It's like having a magic blender that can make any smoothie you need without you listing every fruit.
The New Problem: Even with the magic blender, you still have to choose the recipe (the kernel) and tune its settings (parameters). If you pick the wrong recipe, the smoothie tastes terrible. Until now, picking the right recipe required a lot of human guesswork and trial-and-error.

2. The New Solution: Teaching the Blender to Learn

The authors say, "Why don't we let the computer learn the best recipe itself?" They extend the idea of "dictionary learning" (where computers learn which ingredients to pick) to "kernel learning" (where computers learn the best recipe).

They propose an algorithm that:

Starts with a mix: It takes a weighted list of different, well-known recipes (kernels) with random settings.
Tastes and adjusts: It runs the system, sees how well it predicts the future, and then uses gradient descent (a mathematical way of sliding down a hill to find the lowest point) to tweak the settings of the recipes.
Prunes the list: If a recipe isn't helping, the algorithm turns its weight down to zero. It effectively says, "We don't need this ingredient anymore," and removes it. This leaves a lean, efficient list of only the most useful kernels.

3. The "Simplification" Trick

The paper admits that doing this directly on the original complex math is very hard. So, they invented a simplified version of the method (called skEDMD).

The Analogy: Imagine you want to study a complex machine. The original method tries to take apart the whole engine to see how it works. The authors' new method says, "Let's just look at the specific parts that move when we push a button."
They proved mathematically that this simplified version gives the exact same results as the complex one but is much easier to work with. This allows them to use standard tools (like those used in neural networks) to train the kernels.

4. The Experiments: Testing the New Method

The authors tested their "learning blender" on three different challenges:

The Duffing Oscillator (A bouncing spring): They started with a kernel that was completely wrong (like trying to use a hammer to fix a watch). The algorithm quickly realized it was wrong, adjusted the settings, and found a kernel that perfectly predicted the spring's motion.
The "Modulo" System (A jumping angle): Imagine a clock hand that jumps from 12 back to 1 instantly. This is hard to predict because of the jump. The algorithm was given a mix of kernels: some that handle smooth curves, and one that "wraps" the data to hide the jump. The algorithm quickly realized the "wrapping" kernel was the hero and turned the volume up on it, while turning the volume down on the useless ones.
The Kuramoto-Sivashinsky Equation (Chaotic fluid flow): This is a very messy, chaotic system (like turbulent water). The algorithm started with a huge mix of 6 different kernel types. After training, it kept the two most effective ones (a specific smooth curve and a "neural network" style kernel) and discarded the rest. It successfully predicted the chaotic flow, even though the starting guess was terrible.

5. The "Scheduler" Safety Net

One clever feature they added is a regularization scheduler.

The Analogy: When you first start learning to drive, you need training wheels (heavy regularization) so you don't crash. As you get better, you take the training wheels off.
The algorithm starts with a "safety net" that prevents the math from exploding if the initial guess is bad. As the algorithm learns and gets better, it slowly removes this safety net, allowing the model to become more precise.

Summary

In short, this paper presents a method that automates the search for the best mathematical tools to study complex, chaotic systems. Instead of a human expert guessing which formulas to use, the computer starts with a bag of random formulas, learns which ones work best through trial and error, and throws away the ones that don't. This makes it easier to predict how complex systems (like fluids or oscillators) will behave in the future.

1. Problem Statement

The study of nonlinear dynamical systems often relies on the Koopman operator framework, which transforms nonlinear dynamics into a linear, infinite-dimensional evolution of observables. To approximate this operator in finite dimensions, Extended Dynamic Mode Decomposition (EDMD) is commonly used. However, EDMD requires a manually selected "dictionary" of observables. If the dictionary is too small, the approximation is poor; if too large, it incurs high computational costs and numerical instability (spectral pollution).

Kernel EDMD (kEDMD) addresses the computational bottleneck by implicitly defining the dictionary via a kernel function, allowing the approximation size to be bounded by the number of snapshots ( $N$ ) rather than the dictionary size ( $M$ ). However, kEDMD introduces a new challenge: selecting the appropriate kernel and tuning its hyperparameters. Traditionally, this relies on intuition and manual tuning. While "dictionary learning" (optimizing dictionary parameters via gradients) exists for standard EDMD, it cannot be directly applied to kEDMD because the dictionary in kEDMD is implicit and cannot be explicitly evaluated or differentiated in the standard way.

The Core Problem: How to automate the selection and parameterization of kernels in kEDMD using gradient-based optimization (dictionary learning) without access to the explicit dictionary, while ensuring computational feasibility.

2. Methodology

The authors propose a framework called kEDMD-DL (Dictionary Learning for Kernel EDMD) that bridges the gap between standard dictionary learning and kernel methods.

A. Theoretical Simplification (Simplified kEDMD)

The authors first demonstrate that the standard kEDMD (which uses truncated SVD to reduce dimensionality) is mathematically equivalent to a Simplified kEDMD (skEDMD).

Standard kEDMD: Uses a large implicit dictionary and projects it via SVD to an $N \times N$ matrix ( $\hat{K}$ ).
Simplified kEDMD (skEDMD): Defines the dictionary explicitly as the set of kernel functions centered at the snapshot points: $\Psi = \{g(\cdot, x_1), \dots, g(\cdot, x_N)\}$ .
Equivalence: They prove (Proposition 2) that the Koopman approximation $K_{sk}$ derived from this specific dictionary is linearly related to the truncated SVD approximation $K_{tr}$ . This equivalence allows the authors to apply standard EDMD loss functions directly to the kernel parameters, bypassing the need for complex implicit differentiation of the SVD projection.

B. Loss Functions and Optimization

Since the dictionary in skEDMD is explicit (evaluated at data points), the authors can define various loss functions for gradient descent:

Prediction Loss ( $L_{pred}$ ): Minimizes the error in predicting future states ( $Y^T \approx C_p K \Psi(X)$ ).
Dictionary Loss ( $L_{dict}$ ): Minimizes the residual of the Koopman equation ( $\|\Psi(Y) - K\Psi(X)\|^2$ ).
Eigen-prediction Loss ( $L_{eig-pred}$ ): Minimizes error using Koopman modes and eigenvalues.

Key Finding: Experiments show that Prediction Loss ( $L_{pred}$ ) is the most robust and effective for training, whereas standard dictionary losses often suffer from trivial solutions or instability, especially with single-parameter kernels.

C. Kernel Mixture and Sparsity

To avoid the difficulty of guessing the "correct" kernel type, the method uses a weighted sum of multiple kernels:
$g_\theta(x, y) = \sum_{i=1}^{M_g} \tilde{w}_i^2 g_{\theta_i}(x, y)$

Outer Parameters ( $w_i$ ): Weights for each kernel type.
Inner Parameters ( $\theta_i$ ): Hyperparameters of individual kernels (e.g., RBF width $\sigma$ , linear coefficients).
Sparsity via Pruning: The authors apply $L_1$ regularization to the outer weights ( $w_i$ ) and $L_2$ regularization to inner parameters. This encourages the optimization to drive the weights of unimportant kernels to zero. Post-training, kernels with negligible weights are pruned (removed), resulting in a sparse, efficient kernel representation.

D. Computational Enhancements

To make the training feasible for large datasets:

Stochastic Gradient Descent (SGD): Uses mini-batches to improve generalization and navigate rugged loss landscapes.
Subsampling: The Koopman matrix is computed on a subsampled set of points ( $\tilde{N} \ll N$ ) to reduce computational cost.
Regularization Scheduler: A scheduler dynamically adjusts the regularization constant for the Koopman matrix inversion. It starts high to stabilize training with poor initial kernels and decreases as the kernel improves, preventing loss explosion or premature plateauing.

3. Key Contributions

Extension of Dictionary Learning to Kernels: The paper successfully adapts dictionary learning (previously limited to explicit dictionaries like neural networks) to the implicit setting of kEDMD by proving the equivalence between standard kEDMD and a simplified kernel-based EDMD formulation.
Automated Kernel Selection: It introduces a method to learn both the type of kernel (via weighted sums) and the hyperparameters simultaneously, removing the need for manual kernel selection.
Sparse Kernel Representation: By utilizing $L_1$ regularization on kernel weights, the method automatically identifies and removes irrelevant kernels, leading to parsimonious models.
Robustness to Initialization: The proposed scheduler and loss functions allow the algorithm to converge even when initialized with "bad" kernels (e.g., those producing eigenvalues far outside the unit circle), a common failure point in previous methods.

4. Experimental Results

The method was evaluated on three distinct dynamical systems:

Duffing Oscillator (Single Kernel):
- Trained a single RBF kernel.
- Result: The algorithm successfully learned the optimal bandwidth $\sigma$ , transforming a poor initial linear-like kernel into one that accurately captured the system's dynamics and eigenvalues. Prediction loss was shown to be superior to dictionary loss for optimization.
Modulo System (Kernel Selection):
- A system with a discontinuous jump ( $x_{t+1} = (x_t + \omega) \mod 2\pi$ ).
- Result: The algorithm started with a mix of RBF, linear, cosine, and embedding-based kernels. It correctly identified that the embedding-based kernel (which maps the angle to a circle) was the only useful one, driving the weights of the other three kernels to near zero. The pruned model achieved eigenvalues exactly on the unit circle, matching the theoretical spectrum.
Kuramoto-Sivashinsky PDE (Complex System):
- A chaotic partial differential equation.
- Result: The method learned a mixture of RBF, cosine, linear, and Neural Network Gaussian Process (NNGP) kernels.
- Pruning: After training, the RBF (with specific $\sigma$ ) and NNGP kernels were retained, while others were pruned.
- Performance: The learned kernel significantly reduced the residual of eigenvalues and accurately predicted trajectories, outperforming the initial random kernel. The authors noted that a two-stage training (small $\tilde{N}$ for initial learning/pruning, followed by fine-tuning on larger $\tilde{N}$ ) was an effective strategy to balance cost and accuracy.

5. Significance

This work represents a significant step toward fully automated, data-driven modeling of nonlinear dynamical systems.

Bridging Theory and Practice: It resolves the theoretical gap preventing dictionary learning in kernel methods, making kEDMD a "black-box" friendly tool where the user does not need deep domain knowledge to select kernels.
Efficiency: By enabling the pruning of unimportant kernels, it produces compact models that are computationally efficient for prediction and control.
Scalability: The use of subsampling and SGD makes the approach applicable to high-dimensional systems (like PDEs) where traditional EDMD would be intractable.
Future Impact: The framework opens the door to integrating advanced kernel flows and non-parametric methods into dynamical system analysis, potentially replacing manual feature engineering with learned representations.