🔢 mathematics

Finding Koopman Invariant Subspaces via Personalized PageRank

This paper proposes a method to identify Koopman-invariant subspaces by detecting zero-block structures in Extended Dynamic Mode Decomposition matrices using Personalized PageRank, providing theoretical finite-sample guarantees and demonstrating effectiveness across various dynamical systems.

Original authors: Hyukpyo Hong, Qin Li, Matthew J. Colbrook, Hanbaek Lyu

Published 2026-05-26

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Hyukpyo Hong, Qin Li, Matthew J. Colbrook, Hanbaek Lyu

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

The Big Picture: Predicting the Unpredictable

Imagine you are trying to predict the future path of a chaotic system, like a swirling storm, a bouncing ball on a trampoline, or the movement of molecules in a cell. These systems are nonlinear, meaning they are messy, sensitive to tiny changes, and hard to forecast.

Mathematicians have a powerful tool called the Koopman Operator. Think of it as a "magic lens" that takes this messy, nonlinear world and projects it onto a flat, linear screen. Suddenly, the chaos looks like a simple, straight line. This makes prediction much easier.

However, there is a catch: To use this magic lens, you need a dictionary of "observables" (a list of features to watch, like position, speed, temperature, etc.).

The Problem: If your dictionary is too small, you miss important details. If it's too big, you get overwhelmed by noise, and the math becomes unstable and confusing. It's like trying to find a specific needle in a haystack that is so huge it's falling apart.
The Goal: We need to find the perfect small subset of features that captures the essence of the system without the clutter.

The Solution: The "Koopman Invariant Subspace"

The paper argues that the perfect dictionary exists. It's called a Koopman Invariant Subspace.

The Analogy: Imagine a group of friends (your features) who always stick together. If you start with one friend, the group dynamics ensure you never leave that circle. In math terms, if you pick the right features, the system's future evolution stays inside that group. It doesn't "leak" out to other, irrelevant features.
The Challenge: How do you find this specific group of friends when you have a list of 1,000 potential candidates? You can't check every possible combination; there are too many.

The Method: Turning Math into a Map

The authors propose a clever trick. They take the data they have and build a giant table (a matrix) that shows how every feature influences every other feature.

The Zero-Block Secret: If a perfect "invariant" group exists, this table has a special structure: a giant block of zeros in the bottom-left corner. This means the features in the "good" group don't get influenced by the "bad" group.
The Problem: Finding this zero block by looking at the whole table is like trying to find a specific pattern in a static-filled TV screen.

The Innovation: Personalized PageRank (PPR)

This is where the paper gets creative. They treat the table of features like a social network or a website.

The Network: Imagine every feature is a person. If Feature A influences Feature B, there is a link between them.
The Walker: They imagine a "walker" (a random surfer) moving through this network.
- Standard PageRank (PR): The walker starts at a random person and wanders everywhere. This is good for finding the most popular people in the whole network, but it might miss specific tight-knit groups.
- Personalized PageRank (PPR): The walker starts at a specific "seed" (a feature you care about, like the current position of a planet). The walker is told: "Stay close to this seed and its immediate friends."
The Result: The PPR algorithm ranks the features based on how tightly they are connected to your seed. If a group of features forms a "closed community" (an invariant subspace), the walker gets stuck there. The features in that group get high scores, and the outsiders get low scores.

Why This is Better (The "Starved Node" Metaphor)

The paper proves that Personalized PageRank (PPR) is much better than the standard version for this job.

The Analogy: Imagine a town where some neighborhoods are well-connected (everyone visits everyone), and others have a "starved" house that no one visits from inside the neighborhood.
Standard PR: If the walker gets stuck in a starved house, the whole ranking breaks down. It requires the whole town to be perfectly mixed to work.
PPR: Because the walker starts at a specific seed, they can reach the starved house directly. PPR doesn't care if the neighborhood is perfectly mixed; it only cares if the seed can reach the group. This makes PPR much more robust and accurate at finding the right dictionary.

The Guarantees: Not Just a Guess

The authors didn't just try this and hope it worked. They did the heavy math to prove:

It works with real data: Even if you don't have infinite data, the method finds the right group with a high probability.
Sample Efficiency: You need fewer data points to make PPR work compared to standard methods.
Error Control: They proved that if the algorithm picks a group, the "leakage" (how much the prediction escapes the group) is mathematically bounded by how much the PPR score drops outside that group.

Real-World Tests

They tested this on four different chaotic systems:

Duffing & Van der Pol Oscillators: Mechanical systems that swing back and forth. The method found tiny dictionaries (as small as 5 features) that predicted the future perfectly, beating random guesses and other complex methods.
Lorenz System: The classic "butterfly effect" weather model. The method found a compressed set of features that correctly identified the system's hidden rhythms (spectral geometry).
Ramachandran Potential: A model for how proteins fold. The method successfully identified the key features needed to predict how the molecule moves between different stable shapes.

Summary

In short, this paper solves the "needle in a haystack" problem of predicting chaotic systems.

Old way: Try to guess the right features or use a massive, messy list.
New way: Use Personalized PageRank to "vote" on which features belong together.
Result: You get a small, clean, interpretable list of features that predicts the future accurately, backed by rigorous mathematical proof that it works even with limited data.

Technical Summary: Finding Koopman Invariant Subspaces via Personalized PageRank

Problem Statement
Data-driven approximation of the Koopman operator relies on selecting a finite dictionary of observables whose span is Koopman-invariant. While Extended Dynamic Mode Decomposition (EDMD) provides a matrix representation of the Koopman operator given a dictionary, the choice of dictionary is critical. Large initial dictionaries (e.g., high-degree polynomials or radial basis functions) often lead to ill-conditioned matrices, poor interpretability, and spectral pollution, where accuracy does not monotonically improve with dictionary size. The central challenge is to identify a compact sub-dictionary that spans a Koopman invariant subspace (or an approximately invariant one) from a large initial set, ensuring that the dynamics within the subspace do not "leak" into the complementary observables.

Methodology
The authors propose a framework that exploits the structural properties of the EDMD matrix to identify such sub-dictionaries. The core insight is that if a sub-dictionary spans a Koopman invariant subspace, the corresponding EDMD matrix exhibits an exact zero block in its bottom-left corner (representing the coupling from the invariant subspace to the complement).

The proposed algorithm, EDMD+PPR, proceeds as follows:

EDMD Construction: Compute the EDMD matrix $K_{\tilde{N}, M}$ from a large initial dictionary $\mathcal{D}_{\tilde{N}}$ and $M$ data pairs.
Markov Chain Interpretation: Construct a row-stochastic matrix $P$ by row-normalizing the absolute values of the transpose of the EDMD matrix ( $P = R(|K_{\tilde{N}, M}^\top|)$ ). This interprets the EDMD matrix as a Markov chain where nodes are observables and transition probabilities represent coupling strengths.
Ranking via PPR: Apply Personalized PageRank (PPR) to $P$ using a seed set $S$ of observables (e.g., state coordinates or slow modes). The PPR vector $\pi_S$ ranks observables based on their connectivity to the seed set.
Selection: Select the top- $N$ observables with the highest PPR scores to form the sub-dictionary $\mathcal{D}_N$ .
Refinement: Recompute the EDMD matrix specifically on the selected sub-dictionary to obtain the final predictor.

Key Contributions

Zero-Block Structure and Invariant Subspaces: The paper establishes that any sub-dictionary spanning a Koopman invariant subspace induces an exact zero block in the EDMD matrix, even with finite data (Theorem 2). When the subspace is only approximately invariant, the norm of the off-diagonal block serves as a computable surrogate for prediction error (Proposition 1).
PPR-Based Detection Theory: The authors demonstrate that PPR is superior to standard PageRank (PR) for detecting these zero blocks. While standard PR requires the internal block of the Markov chain to be "well-mixed" (a condition that fails if "starved" nodes exist), PPR only requires that the seed set can reach all nodes in the target block (Theorem 3). This allows PPR to succeed with a broader range of damping factors $\alpha$ and in the presence of structural bottlenecks.
Finite-Sample Guarantees: By combining EDMD concentration bounds with PageRank perturbation theory, the authors derive end-to-end detection guarantees with an $O(1/\sqrt{M})$ finite-sample scaling rate and explicit constants (Theorem 4). They show that PPR requires fewer samples than standard PR to achieve correct detection (Corollary 4.1).
Unconditional Leakage Bounds: Even without assuming an invariant subspace exists, the paper proves that the multi-step prediction error of a selected sub-dictionary is bounded by the PPR mass falling outside that sub-dictionary (Proposition 9). This provides a principled justification for the method based purely on prediction accuracy.

Results
Numerical experiments on the Duffing oscillator, Van der Pol oscillator, Lorenz system, and a three-well Ramachandran potential validate the method:

Accuracy: The PPR-selected sub-dictionaries achieve significantly lower one-step and multi-step prediction errors compared to random ordering, incremental ordering, standard PR, TICA, and PCCA+. For instance, in the Ramachandran potential, PPR reduced one-step error by approximately 70% compared to random selection at small sub-dictionary sizes ( $N=5$ ).
Interpretability: The selected observables are physically meaningful. In the Ramachandran example, PPR correctly prioritized state coordinates and basin-boundary RBFs, which capture inter-basin transitions.
Spectral Recovery: In the chaotic Lorenz system, PPR-selected sub-dictionaries recovered the characteristic oscillatory pseudo-eigenfunctions at smaller dictionary sizes ( $N=30\text{--}60$ ) compared to incremental ordering ( $N \ge 120$ ).
Robustness: The method successfully identified approximate zero blocks in systems with stochastic dynamics (Ramachandran) and ergodic trajectory data (Lorenz), despite the theoretical guarantees being derived for deterministic, i.i.d. samples.

Significance and Claims
The paper claims to provide a rigorous, data-driven method for dictionary selection that bridges the gap between Koopman operator theory and graph-theoretic community detection. By reinterpreting the EDMD matrix as a Markov chain, the method transforms the combinatorial problem of finding invariant subspaces into a tractable ranking problem. The authors emphasize that their approach offers stronger theoretical guarantees than existing subspace decomposition methods (like TSSD) by providing explicit sample complexity bounds and perturbation analysis. Furthermore, the use of PPR over standard PR addresses structural limitations in the data (such as starved nodes) that would otherwise prevent the detection of invariant subspaces. The work suggests that high PPR mass on a sub-dictionary effectively minimizes "leakage," ensuring that the dynamics remain confined within the selected subspace, thereby enabling accurate long-term predictions with compact, interpretable models.