⚡ electrical engineering

Subspace Pruning via Principal Vectors for Accurate Koopman-Based Approximations

This paper proposes a unified algebraic framework for subspace pruning based on principal vectors to systematically refine Koopman operator invariance, introducing a hybrid strategy and efficient numerical updates that balance invariance improvement with state reconstruction accuracy for scalable linear state prediction.

Original authors: Dhruv Shah, Jorge Cortés

Published 2026-05-14

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Dhruv Shah, Jorge Cortés

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 future path of a swirling tornado or a chaotic pendulum. These systems are messy and non-linear, meaning they don't follow simple, straight lines. However, there is a mathematical tool called the Koopman operator that tries to turn this chaos into a simple, straight line. It does this by looking at the system not from the outside, but by watching a whole library of "observable functions" (like temperature, speed, or position) evolve over time.

The problem is that this library is infinite. To use it on a computer, we have to pick a finite "dictionary" of functions to work with. But here's the catch: if we pick the wrong dictionary, our predictions might look good for one second, but they will spiral out of control after a few minutes. This happens because the chosen functions "leak" out of the system we built, breaking the math.

This paper, by Dhruv Shah and Jorge Cortés, is about cleaning up that dictionary to make sure the math stays solid for the long haul. Here is how they do it, explained through simple analogies:

1. The "Leaky Bucket" Problem

Think of your chosen dictionary of functions as a bucket. You want to pour water (the system's dynamics) into this bucket and have it stay there forever.

The Old Way: Most methods just try to make sure the water doesn't spill out immediately (one step at a time). But if the bucket has a tiny hole, the water will eventually drain away, and your long-term prediction will be wrong.
The Paper's Goal: They want to find a bucket that is perfectly sealed (mathematically "invariant"), so the water stays in forever. Since a perfect bucket is rare, they aim to find one that is "close enough" to sealed.

2. The "Principal Vectors" as Leaks

How do they find the holes? They use a geometric concept called Principal Vectors.
Imagine your bucket is a room, and the water is trying to escape through the walls. The "Principal Vectors" are like a laser scanner that points directly at the biggest cracks in the wall.

The scanner tells them: "Hey, this specific direction in your dictionary is the one leaking the most water."
The paper proposes pruning (cutting out) these specific directions to seal the bucket.

3. Two Ways to Cut the Cracks

The authors propose two different strategies for fixing the leaks, and they found that doing it one way at a time isn't always the best.

The "Single Vector" (SPV) Approach: This is like using a tiny screwdriver to fix one crack at a time. You find the biggest leak, patch it, then find the next biggest.
- Pros: It's very careful and precise.
- Cons: If you have a huge bucket with thousands of cracks, fixing them one by one takes forever. Also, the tiny screwdriver can sometimes make the metal slightly wobbly (numerical drift), causing you to accidentally patch a good spot instead of a bad one.
The "Multiple Vector" (MPV) Approach: This is like bringing in a bulldozer. You identify all the cracks that are bigger than a certain size and knock them all out at once.
- Pros: It's incredibly fast.
- Cons: It's too aggressive. You might knock out a wall that was actually holding up the roof (a useful function), leaving you with a bucket that is too small to hold the water you need.

4. The "Hybrid" Solution: The Best of Both Worlds

The paper's big breakthrough is a Hybrid Strategy.
Imagine you are cleaning a messy attic.

Step 1 (The Bulldozer): First, you use the bulldozer (MPV) to quickly clear out the obvious, massive piles of junk that are definitely trash. You do this with a "loose" rule, just getting rid of the worst offenders.
Step 2 (The Screwdriver): Now that the attic is much smaller, you switch to the tiny screwdriver (SPV). You carefully go through the remaining items to fine-tune the space, fixing the small leaks without accidentally throwing away anything useful.

This combination is fast (because the bulldozer did the heavy lifting) but also precise (because the screwdriver did the fine work). It prevents the "wobbly metal" problem of doing it all one-by-one, and it prevents the "over-cleaning" problem of doing it all at once.

5. The "Magic Calculator" Trick

Doing these calculations usually requires a supercomputer because the math gets heavy very quickly. The authors invented a fast update trick.
Instead of recalculating the entire geometry of the bucket from scratch every time they cut a piece out, they use a "rank-one update."

Analogy: Imagine you have a giant map of a city. If you close one street, you don't need to redraw the whole map. You just make a tiny, specific edit to the existing map.
This trick makes the process 10 times faster, allowing them to clean up massive dictionaries of functions in seconds rather than hours.

6. The Final Result: A Reliable Predictor

Once they have this "cleaned" dictionary, they build a linear model (a simple, straight-line prediction machine).

They tested this on a Van der Pol oscillator (a classic, wobbly, non-linear system).
The Result: Their pruned model could predict the system's behavior for a very long time without drifting off course. Other methods (like standard EDMD or Kernel EDMD) either drifted away quickly or were unstable.

Summary

In short, this paper provides a smart, fast, and safe way to clean up a messy dictionary of functions so that we can use simple linear math to predict complex, chaotic systems accurately over long periods. They achieved this by combining a "big hammer" approach with a "fine needle" approach, and by inventing a shortcut to do the math quickly.

Technical Summary: Subspace Pruning via Principal Vectors for Accurate Koopman-Based Approximations

Problem Statement
The practical implementation of the Koopman operator for nonlinear dynamical systems relies on finite-dimensional approximations, typically constructed via projection methods like Extended Dynamic Mode Decomposition (EDMD). A critical limitation of standard EDMD is that it minimizes one-step prediction residuals without guaranteeing that the chosen subspace is invariant under the Koopman operator. When a subspace is not invariant, the dynamics "leak" out of the subspace upon iteration, causing geometric accumulation of errors that renders long-term predictions unreliable. While existing methods attempt to identify invariant subspaces, they often lack rigorous geometric foundations or suffer from numerical instability when applied to large, overparameterized dictionaries of basis functions. The core challenge is to systematically refine a candidate dictionary to find a subspace that satisfies a user-specified invariance tolerance while preserving the expressivity required for state reconstruction.

Methodology
The paper proposes a unified algebraic framework for subspace pruning based on the geometric concept of principal angles and principal vectors between a candidate subspace $S$ and its image $KS$ under the Koopman operator.

Geometric Formulation: The quality of an approximation is quantified by the invariance proximity $\delta(S)$ , defined as the sine of the maximum principal angle between $S$ and $KS$. Minimizing $\delta(S)$ directly minimizes the worst-case relative prediction error.
Pruning Algorithms:
- Single Principal Vector (SPV) Pruning: An iterative algorithm that identifies the principal vector corresponding to the largest principal angle (the direction with the most significant "leakage") and removes it from the dictionary. The authors prove that SPV is algebraically equivalent to the Recursive Forward-Backward EDMD (RFB-EDMD) algorithm, establishing that the eigenvectors of the RFB-EDMD consistency matrix are precisely the principal vectors of the subspace.
- Multiple Principal Vector (MPV) Pruning: A strategy that removes all principal vectors violating the invariance tolerance $\epsilon$ simultaneously in a single batch. While computationally efficient, the paper demonstrates that aggressive MPV pruning can lead to significant "numerical drift," causing the loss of approximate eigenfunctions that should be retained.
- Hybrid MPV-SPV Strategy: To balance efficiency and stability, the authors introduce a hybrid approach. It first applies MPV with a relaxed tolerance to rapidly eliminate the most non-invariant directions, followed by SPV with the strict target tolerance to fine-tune the subspace. This mitigates the cumulative numerical drift inherent in sequential SPV while avoiding the over-aggressive information loss of pure MPV.
Efficient Computation: To ensure scalability for large dictionaries, the paper develops a numerical update scheme based on rank-one modifications and incremental QR decompositions. This allows the recomputation of principal angles and vectors after pruning without performing a full Singular Value Decomposition (SVD) at every step, reducing computational complexity by an order of magnitude.
State Prediction Framework: The pruned subspace is utilized to construct a lifted linear model. The authors propose a decoupled architecture where the dynamics are evolved within the invariant subspace, and an auxiliary lifting map reconstructs the original state, allowing designers to trade off between invariance (long-term stability) and reconstruction accuracy (short-term fidelity).

Key Contributions

Geometric Unification: The paper establishes the algebraic equivalence between consistency-based pruning (RFB-EDMD) and principal-vector pruning, providing a geometric interpretation of consistency indices via principal angles.
Novel Pruning Algorithms: The introduction of the MPV algorithm and the Hybrid MPV-SPV strategy. The hybrid approach is specifically designed to mitigate the numerical drift observed in sequential pruning, ensuring better retention of approximate eigenfunctions.
Retention Analysis: Theoretical bounds are derived for the retention of "external" eigenfunctions (those slightly outside the initial dictionary due to finite precision). The analysis proves that the multi-vector approach significantly improves the retention of these functions by reducing cumulative error amplification.
Computational Efficiency: The development of an efficient update scheme using rank-one corrections and incremental QR updates, which drastically reduces the cost of iterative pruning for large-scale problems.
Balanced Modeling: A framework for constructing lifted linear models that explicitly manages the trade-off between minimizing invariance error and minimizing state reconstruction error.

Results
Numerical experiments on a 2D nonlinear system and the Van Der Pol oscillator validate the proposed methods:

Accuracy: The Hybrid MPV-SPV algorithm outperforms both pure SPV and pure MPV in terms of accuracy. It successfully recovers a subspace containing the true eigenfunctions of the system with minimal numerical drift, whereas naive iterative methods degrade in accuracy as the dictionary size increases.
Efficiency: Benchmarks show that the rank-one update scheme reduces wall-clock time significantly, particularly for large dictionary sizes. The overhead of the pruning steps is minimal compared to the initial SVD computation.
Prediction Performance: In the Van Der Pol oscillator simulation, the pruned model (dimension $s=12$ ) demonstrated superior long-term prediction accuracy compared to standard EDMD and kernel EDMD (dimension $s=289$ ). While kernel EDMD offered better short-term estimates, it became unstable over time, whereas the pruned model maintained low error in both the lifted state and the reconstructed physical state over 3000 time steps.

Significance
The paper claims that its primary significance lies in providing a rigorous, scalable, and numerically stable algebraic framework for constructing Koopman models with guaranteed structural invariance. By linking consistency-based methods to principal vector geometry, the work offers a theoretical explanation for numerical drift in sequential pruning and provides a practical solution (the hybrid strategy) to mitigate it. The ability to efficiently track principal angles via rank-one updates makes these rigorous pruning techniques feasible for large-scale, data-driven applications. Ultimately, the framework addresses the critical need for reliable long-horizon forecasting and accurate eigenfunction approximation, which are essential for data-driven control and stability analysis in complex nonlinear systems.