Koopman Subspace Pruning in Reproducing Kernel Hilbert Spaces via Principal Vectors

1. Problem Statement

The paper addresses a critical limitation in data-driven modeling of nonlinear dynamical systems using the Koopman operator.

• Context: The Koopman operator framework lifts nonlinear dynamics into an infinite-dimensional linear space of observables. Practical implementations, such as Extended Dynamic Mode Decomposition (EDMD) and its kernel-based variant (Kernel EDMD), approximate this operator by projecting it onto a finite-dimensional subspace spanned by a dictionary of functions.
• The Challenge: The accuracy of these approximations depends heavily on the invariance proximity of the chosen subspace. If the subspace is not invariant under the Koopman operator (i.e., the operator maps functions out of the subspace), projection errors occur, leading to poor predictive performance.
• Existing Gap: While "subspace pruning" techniques exist to remove geometrically misaligned directions and improve invariance in standard Euclidean settings (using $L_2$ inner products), they have not been extended to Reproducing Kernel Hilbert Spaces (RKHS).
• Specific Obstacles:
  1. Geometry: Computing principal angles (a measure of invariance) in RKHS is non-trivial because the dictionary elements are implicit linear combinations of kernel sections, not explicit vectors.
  2. Scalability: Exact Kernel EDMD and the associated pruning procedures require operations on $N \times N$ kernel matrices (where $N$ is the number of data points), resulting in $O(N^3)$ computational complexity, which is prohibitive for large datasets.

2. Methodology

The authors propose a framework to compute principal angles and vectors within an RKHS geometry to enable subspace pruning, offering both an exact method and a scalable approximation.

A. Theoretical Foundation: RKHS Principal Angles

The paper defines the invariance proximity $\delta(S)$ as the sine of the largest principal angle between a subspace $S$ and its image under the Koopman operator, $KS$.

• Exact Computation (Kernel-SPV):
  • The authors derive an algebraic routine to compute principal angles without explicitly constructing the infinite-dimensional functions.
  • They utilize the kernel trick to express inner products via kernel matrices ($K_{X,X}$ and $K_{T(X),X}$).
  • Key Derivation: They establish that the basis vectors of the Koopman image ($KV$) can be represented as linear combinations of the data kernel sections ($\Phi_X$) by solving a linear system: $K_{X,X} W_{KV} = K_{T(X),X} W_V$.
  • Orthogonalization: Since the Gram matrices may be rank-deficient, the method employs truncated eigendecompositions to obtain stable, orthonormal bases for the subspaces.
  • SVD: The principal angles and vectors are finally extracted via the Singular Value Decomposition (SVD) of a "cosine matrix" constructed from these orthonormal bases.

B. Scalable Approximation: Nyström Method (Approximate Kernel-SPV)

To overcome the $O(N^3)$ bottleneck, the authors introduce a scalable approach using Nyström approximation.

• Landmark Sampling: A small subset of $D \ll N$ "landmark" points is selected from the dataset.
• Feature Map Construction: An explicit finite-dimensional feature map $\psi: \mathbb{R}^n \to \mathbb{R}^D$ is constructed using the eigendecomposition of the landmark kernel matrix. This allows the kernel matrix $K_{X,X}$ to be approximated as $\Psi(X)^\top \Psi(X)$.
• Target Matrix Design:
  • Instead of solving the expensive $O(N^3)$ linear system for the Koopman image coefficients, the method constructs target matrices ($Z_V$ and $Z_{KV}$) directly in the feature space.
  • A Tikhonov-regularized solution is used to compute the Koopman image target, ensuring numerical stability and bypassing the inversion of the full kernel matrix.
• Rank Separation: To handle the rank inflation caused by the approximation and regularization, the authors apply truncated SVD with data-dependent thresholds to the target matrices. This ensures the computed subspaces match the true geometric ranks of the underlying problem.
• Complexity: The complexity is reduced from $O(N^3)$ to $O(NDs + D^3)$, where $s$ is the subspace dimension and $D$ is the number of landmarks.

C. The Pruning Algorithm (SPV)

The computed principal vectors are used in an iterative Single Principal Vector (SPV) pruning strategy:

1. Compute principal angles between the current subspace and its Koopman image.
2. Identify the principal vector associated with the largest angle (the direction least invariant).
3. Remove this direction from the dictionary.
4. Repeat until the invariance proximity falls below a specified tolerance $\epsilon$.

3. Key Contributions

1. RKHS Formulation: The first rigorous derivation of principal angles and vectors specifically for the RKHS geometry, enabling subspace pruning for Kernel EDMD.
2. Exact Algorithm (Kernel-SPV): A computational routine that solves the principal angle problem using Gram matrices and spectral truncation, providing a theoretical baseline.
3. Scalable Algorithm (Approximate Kernel-SPV): A novel integration of Nyström approximation and Tikhonov regularization that allows subspace pruning on massive datasets ($N \gg D$) with linear complexity relative to $N$.
4. Theoretical Justification: Proof that the Nyström-based approximation converges to the true principal arguments and that the regularization preserves the geometric structure necessary for pruning.

4. Simulation Results

The authors validated their approach using a damped Duffing oscillator ($N=5000$ data points).

• Convergence: As the number of Nyström landmarks ($D$) increased, the orthonormality residuals of the approximate bases decreased, confirming convergence to the exact RKHS geometry.
• Accuracy: With $D=2000$, the approximate method successfully identified the same invariant subspace as the exact method, despite the bases not being perfectly orthonormal. This indicates the method captures the essential geometry for pruning efficiently.
• Performance Improvement:
  • Pruning reduced the subspace dimension from $s=200$ to $s^*=5$.
  • Prediction Error: The 5-step prediction error for the leading Koopman eigenfunction (critical for long-term dynamics) was significantly reduced after pruning compared to the unpruned Kernel EDMD model.

5. Significance

• Bridging Theory and Practice: This work unifies the rich, data-dependent dictionaries of RKHS with the model reduction capabilities of subspace pruning, addressing a gap where previous pruning methods were limited to Euclidean settings.
• Scalability: By reducing computational complexity from cubic to near-linear, the paper makes high-fidelity Koopman modeling and model reduction feasible for large-scale dynamical systems and massive datasets.
• Control Applications: The resulting reduced-order models are crucial for synthesizing tractable controllers based on lifted state dynamics, a key requirement in modern control theory.
• Robustness: The introduction of regularization and rank-separation thresholds ensures the method is numerically stable even when dealing with noisy data or ill-conditioned kernel matrices.

In summary, the paper provides a complete mathematical and algorithmic framework to refine Koopman models in RKHS, ensuring higher predictive accuracy and computational efficiency through principled subspace pruning.