⚡ electrical engineering

A Unified Algebraic Framework for Subspace Pruning in Koopman Operator Approximation via Principal Vectors

This paper proposes a unified algebraic framework for subspace pruning in Koopman operator approximation that utilizes principal vectors to minimize invariance error, establishes its equivalence to existing consistency-based methods, and introduces an efficient rank-one update scheme to significantly reduce computational complexity.

Original authors: Dhruv Shah, Jorge Cortes

Published 2026-04-01

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Dhruv Shah, Jorge Cortes

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 weather. The atmosphere is a chaotic, messy, non-linear system (wind, heat, pressure all interacting in complex ways). It's hard to model.

Now, imagine you have a magic lens that, instead of looking at the messy weather, lets you see the underlying "skeleton" of the system. Suddenly, the chaos looks like a simple, straight line. This is the Koopman Operator. It's a mathematical tool that turns a messy, non-linear world into a clean, linear one, making it much easier to predict the future.

However, there's a catch. To use this magic lens, you have to choose a specific "view" or subspace (a limited set of tools) to look through. If you pick the wrong tools, your view will be blurry, and your predictions will fail after just a few steps. You need a view that stays "invariant"—meaning the rules of the system don't break when you look at them tomorrow.

The Problem: The "Leaky Bucket"

The authors of this paper are trying to solve a specific problem: How do we find the perfect view?

Imagine you have a giant bucket full of water (your data and potential models). Some parts of the bucket are solid, but some have holes in them. If you try to carry water in a bucket with holes, it leaks out. In math terms, the "leak" is the error in your prediction.

Current methods try to fix this by checking the bucket, finding the biggest hole, plugging it, and then checking again. But doing this is like trying to fix a leaky boat by draining the whole ocean every time you find a hole. It's incredibly slow and computationally expensive, especially when you have a massive bucket (lots of data).

The Solution: A New Way to Plug Holes

The paper proposes a unified, algebraic framework to fix this. Here is the breakdown of their three main contributions, explained simply:

1. The "Principal Angle" Compass

To find the holes, the authors use a concept called Principal Angles.

The Analogy: Imagine you have a shadow cast by an object (your current model) and the shadow of that object one second later (where the system actually goes).
The Problem: If the object is perfectly stable, the two shadows line up perfectly. If the object is unstable, the shadows drift apart.
The Metric: The "Principal Angle" measures exactly how much the shadows drift apart. A large angle means a big leak (bad model). A zero angle means a perfect fit.
The Innovation: The authors show that you can use these angles to systematically identify exactly which part of your model is causing the leak.

2. The "Single-Principal-Vector" (SPV) Pruning

Once they know where the leak is, they need to fix it. They propose a strategy called SPV Pruning.

The Analogy: Imagine you are sculpting a statue out of a block of marble. You want the final statue to be perfect, but you started with a block that has some ugly, jagged edges (the bad parts of your model).
The Method: Instead of guessing which chisel to use, the SPV method looks at the statue, finds the single worst jagged edge (the direction with the biggest angle/leak), and slices it off. Then it looks again, finds the next worst edge, and slices that off too.
The Result: You are left with a smooth, perfect statue (a highly accurate, invariant model) that is smaller but much better than the original messy block.

3. The "Magic Shortcut" (Rank-One Updates)

This is the most technical but also the most exciting part for speed.

The Old Way: Every time you slice off a piece of the marble, the old method would say, "Okay, let's measure the entire statue again from scratch to see how the angles changed." If your statue is huge, this takes forever.
The New Way: The authors realized that when you slice off a tiny piece, you don't need to re-measure the whole thing. You only need to calculate the change caused by that one slice.
The Analogy: Imagine you are updating a spreadsheet. The old way is to re-calculate the sum of a million numbers every time you change one cell. The new way is to just add the difference of that one cell to the previous total.
The Impact: This "Rank-One Update" makes the process 10 to 100 times faster. It turns a task that would take hours into one that takes seconds, making it possible to use these powerful models on massive datasets.

Why Does This Matter?

Better Predictions: By removing the "leaky" parts of the model, the remaining model is much more accurate over long periods. It doesn't just predict the next second; it predicts the next hour or day.
Speed: Because they made the math so efficient, we can now apply these complex physics models to real-world problems (like controlling drones, managing power grids, or understanding climate change) that were previously too slow to compute.
Unification: They proved that their new "geometric" way of thinking is actually the same as older "consistency" methods, but their new way is more flexible and easier to expand for future problems.

Summary

The paper is about building a better telescope for looking at chaotic systems. They figured out how to identify the blurry parts of the image, cut them out one by one, and invented a super-fast way to do the cutting so we can see the future clearly without waiting years for the computer to finish the math.

1. Problem Statement

The Koopman operator provides a powerful framework for analyzing nonlinear dynamical systems by lifting them into an infinite-dimensional linear space of observable functions. However, practical applications require finite-dimensional approximations, typically achieved via Extended Dynamic Mode Decomposition (EDMD).

The Core Challenge:
Standard EDMD approximations often fail to provide robust long-term predictions because the chosen finite-dimensional subspace is rarely strictly invariant under the Koopman operator. When a subspace is not invariant, the projection of the dynamics onto the subspace discards components orthogonal to it, leading to "leakage" and significant prediction errors.

Goal: The paper aims to solve the Invariant Subspace Search Problem: Given an initial large dictionary of candidate functions (subspace $S_{init}$ ), find a subspace $S^*$ of the maximum possible dimension such that the invariance proximity (a measure of how close the subspace is to being invariant) is below a user-defined tolerance $\epsilon$ .
Constraint: The solution must be computationally efficient, as naive search methods involve combinatorial explosions, and standard optimization (e.g., neural networks) lacks deterministic guarantees.

2. Methodology

The authors propose a unified geometric and algebraic framework centered on Principal Angles and Vectors.

A. Geometric Foundation: Invariance Proximity

The quality of an approximation is quantified by the invariance proximity $\delta(S)$ , defined as the sine of the largest principal angle ( $\theta_{max}$ ) between the subspace $S$ and its image under the Koopman operator $KS$.

$\delta(S) = \sin(\theta_{max})$ .
$\delta(S) = 0$ implies strict invariance.
Theorem 2.5 establishes that $\delta(S)$ exactly corresponds to the worst-case relative prediction error of the EDMD model.

B. The SPV Pruning Algorithm

To solve the search problem, the authors introduce the Single-Principal-Vector (SPV) pruning strategy:

Identify: Compute the principal angles and vectors between the current subspace $S$ and its image $KS$.
Select: Identify the principal vector $u_{max}$ in $S$ corresponding to the largest principal angle (the "worst offender" causing the most leakage).
Prune: Remove the direction spanned by $u_{max}$ from the subspace ( $S_{new} = S \setminus \text{span}(u_{max})$ ).
Iterate: Repeat until the maximum principal angle falls below the tolerance $\epsilon$ .

C. Theoretical Unification

The paper proves a critical theoretical result: The SPV algorithm is algebraically equivalent to the Recursive Forward-Backward EDMD (RFB-EDMD) algorithm.

RFB-EDMD uses a "consistency matrix" ( $M_c = I - K_f K_b$ ) to prune directions.
The authors demonstrate that the eigenvalues of $M_c$ are exactly the squared sines of the principal angles ( $\sin^2 \theta_i$ ), and its eigenvectors correspond to the principal vectors.
Significance: This unifies existing consistency-based methods under a broader geometric framework, showing that RFB-EDMD is a specific instance of SPV pruning under the empirical $L_2$ inner product.

D. Efficient Numerical Implementation (Rank-One Updates)

A naive implementation of SPV requires recomputing the full Singular Value Decomposition (SVD) at every pruning step, resulting in $O(s^3)$ complexity per iteration (where $s$ is the dictionary size). To ensure scalability, the authors develop an efficient update scheme:

Rank-One Modification: Instead of full SVD, they formulate the update of principal angles as a symmetric rank-one modification of an eigenproblem.
Incremental QR: They maintain the QR decomposition of the image matrix. When a basis vector is removed, they update the QR factors incrementally using the smaller triangular matrix $R$ rather than the full data matrix.
Complexity Reduction: This reduces the computational cost of updating principal angles from $O(s^3)$ to $O(s^2)$ per iteration, leveraging LAPACK routines (DLAED9) for symmetric rank-one updates.

3. Key Contributions

Unified Framework: Established a geometric framework for subspace pruning based on principal angles, proving its equivalence to existing consistency-based methods (RFB-EDMD) while generalizing to arbitrary inner product spaces.
SPV Algorithm: Proposed a systematic, iterative pruning strategy that surgically removes the specific directions responsible for invariance violations, maximizing the dimension of the resulting invariant subspace.
Computational Efficiency: Developed a novel numerical scheme using symmetric rank-one updates and incremental QR decompositions. This reduces the complexity of tracking principal angles by an order of magnitude, making the approach viable for large dictionaries and high-dimensional data.
Rigorous Guarantees: Provided deterministic bounds on the approximation error via the invariance proximity metric, avoiding the non-convex optimization landscapes of learning-based dictionary methods.

4. Simulation Results

The authors validated their framework using a damped Duffing oscillator (a nonlinear system with two stable equilibria and an unstable origin).

Efficiency Benchmark:
- Tested on dictionary sizes $s \in \{28, 103, 403\}$ with $N=50,000$ data points.
- Results: The rank-one update scheme (SPV-Rank-1) was significantly faster than the naive SVD approach.
  - For $s=403$ , the naive approach took 134.6 seconds, while the proposed method took only 6.4 seconds (approx. 21x speedup).
Quality Improvement:
- Applied SPV pruning to reduce a dictionary of 503 functions to 15.
- The resulting leading non-trivial Koopman eigenfunction was significantly smoother and provided a clearer separation of the basins of attraction for the system's equilibria compared to the unpruned approximation.

5. Significance

This work bridges the gap between theoretical geometric analysis and practical, scalable data-driven control.

Scalability: By reducing the computational bottleneck, it enables the use of large, expressive dictionaries (necessary for complex nonlinear systems) without prohibitive computational costs.
Generality: The framework is not limited to the standard empirical $L_2$ inner product; it applies to any Hilbert space, opening doors for future generalizations in different function spaces.
Robustness: It offers a deterministic, algebraic alternative to heuristic or learning-based dictionary selection, ensuring that the resulting Koopman models are robust for long-term prediction and control synthesis.