Research map / Learning theory and algorithms / Matrix and tensor methods

Finding Koopman Invariant Subspaces via Personalized PageRank

NeurIPS 2026 · Learning theory and algorithms › Matrix and tensor methods · approach: Low-rank approximation theory · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Shows that Koopman-invariant sub-dictionaries induce exact zero blocks in finite-data EDMD matrices, and proposes row-normalized (personalized) PageRank on the EDMD matrix to detect them, with finite-sample O(1/sqrt(M)) guarantees.

Problem

Selecting a small sub-dictionary of observables from a large initial dictionary whose span is (approximately) Koopman-invariant, so that EDMD predictions are accurate and interpretable; EDMD accuracy is non-monotone in dictionary size and exhaustive subset search is combinatorially prohibitive.

Approach

Interpret the row-normalized transpose of the EDMD matrix as a Markov chain on observables; invariant sub-dictionaries appear as exact zero blocks, which personalized PageRank seeded at target observables detects at any damping factor, with perturbation and finite-sample guarantees.

Key results

• On Duffing and Van der Pol with 90 Laguerre polynomials and M=2000, PPR-selected 5-observable sub-dictionary achieves ~1e-12 one-step error.
• On the Ramachandran potential (N~236 dictionary), PPR at N=5 reduces one-step error by about 70% relative to random ordering, versus 32% for PCCA+ and 6% for TICA.
• Table ratio of error to random: PPR 0.30 at N=5, PR 1.09 at N=5, indicating standard PR can underperform random ordering.

Surprising findings

• Standard PageRank and TICA degrade as sub-dictionary size grows, underperforming even random ordering on the Ramachandran benchmark.
• The Ramachandran experiment is stochastic and falls outside the deterministic theory, yet PPR still performs well empirically.

Limitations

• Theory assumes noise-free i.i.d. samples and a deterministic system; trajectory (Lorenz) and stochastic (Ramachandran) cases are only empirically tested.
• Sub-dictionaries are restricted to subsets of a prescribed initial dictionary; exact invariant subspaces beyond this are not constructed.
• Detection requires choosing damping alpha and seed set; adaptive selection of alpha is left open.

Experimental setup

Datasets: Duffing oscillator simulated data Van der Pol oscillator simulated data Lorenz system trajectory data Three-well Ramachandran potential Langevin simulation data

Benchmarks: Duffing oscillator Van der Pol oscillator Lorenz system three-well Ramachandran potential

Metrics: one-step prediction error multi-step state prediction error ratio of error to random ordering pseudo-eigenfunction recovery

Baselines: PageRank (standard PR) PCCA+ TICA random ordering Incremental ordering

Builds on: extended dynamic mode decomposition PageRank Personalized PageRank Conradie et al. principal angle dictionary compression Perron cluster analysis (PCCA+)

Closest papers by meaning

• Deep-Koopman-KANDy: Dictionary Discovery for Deep-Koopman Operators with Kolmogorov-Arnold Networks for Dynamics (NeurIPS 2026 · similarity 0.87)
• Efficient Parametric SVD of Koopman Operator for Stochastic Dynamical Systems (NeurIPS 2025 · similarity 0.86)
• ResKoopNet: Learning Koopman Representations for Complex Dynamics with Spectral Residuals (ICML 2025 · similarity 0.84)
• KoopSTD: Reliable Similarity Analysis between Dynamical Systems via Approximating Koopman Spectrum with Timescale Decoupling (ICML 2025 · similarity 0.83)
• Complexity of Classical Acceleration for $\ell_1$-Regularized PageRank (NeurIPS 2026 · similarity 0.83)
• Invariant subspaces and PCA in nearly matrix multiplication time (NeurIPS 2024 · similarity 0.83)