Randomized Methods for Kernelized DMD

Peter Oehme · 2026

Read Randomized Methods for Kernelized DMD by Peter Oehme (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-22867.txt.

Introduction

Peter Oehme looks for faster ways to run Dynamic Mode Decomposition on very large datasets. The method, tied to Koopman operator theory, pulls the main patterns of motion out of snapshots of a system. It is used for fluids, power grids, and other systems that change over time.

For huge data, the standard method can be too slow, so randomized shortcuts are tested. Random sampling can cut the cost while keeping the main patterns intact. Faster pattern-finding means engineers can watch complex systems in near real time. Randomized techniques suit this setting because they trade a little precision for very large savings in time and memory.

Catalog record

CREATORPeter Oehme
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE29 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-22867

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Randomized Methods for Kernelized DMD Peter Oehme Abstract Dynamic Mode Decomposition (DMD) is a data-driven method related to Koopman operator theory that extracts information about dominant dynamics from data snapshots. In this paper we examine techniques to accelerate the application of DMD to large-scale data sets with an eye on randomized techniques. Randomized techniques exploit low-rank matrix approximations at a much smaller computational cost, therefore permitting the use of increased data set sizes. In particular, we propose the application of the RPCholesky algorithm in the setting of kernelized DMD (KDMD). This algorithm relies on adaptive randomized sampling to approximate positive semidefinite kernel matrices and provides better stability guarantees than previously implemented randomized methods for KDMD. Differences between existing competitive randomized techniques and our proposed implementation are discussed with a focus on numerical stability and tradeoff between exploration and exploitation of information obtained from data. The efficacy of this new combination of algorithms is demonstrated on well-established benchmark problems from DMD literature increasing in problem dimension. \UKvardate 1 Introduction Dynamic mode decomposition (DMD) is a numerical method that aims to extract the dominant dynamics from sequential snapshots of some underlying nonlinear dynamical system in the form of DMD modes [ 15 ] . The DMD modes are derived from the left eigenvectors of the finite-dimensional projections of the so-called Koopman operator — the operator mapping nonlinear observables of the system’s state forward in time. For this purpose, multiple algorithms have been developped [ 18 , 5 ] many of which focus on particular attributes such as structure preservation or the induction of sparsity. One of the constraints of dynamic mode decomposition is that datasets with large state dimensions N and large numbers of snapshots M require a lot of computational effort. This is a clear bottleneck of DMD and multiple methods have been proposed aiming to remedy this constraint. A prominent technique is kernelized DMD (KDMD) [ 21 ] , where one applies the kernel trick [ 16 , 2 ] to the input data, thus reducing the effects of the large state dimension N . The resulting algorithm, however, requires the solution of two M\times M eigenproblems and therefore does not provide a good scaling with the number of snapshots. On the other hand, Randomized Fourier features (RFF) [ 14 ] provide an approach to only approximate the kernel function involved in KDMD, and then use these features in the extended DMD (EDMD) algorithm [ 6 ] as the nonlinear observables. RFF is based on an analytic relation between the kernel function and a probability measure, allowing for a randomized approach. The principal issue of RFF is the slow convergence of the randomized approximation [ 17 ] , but it has been observed that RFF still reesults in good nonlinear feature maps. Alternatively, one may use algebraic methods for kernel approximations, in particular for symmetric positive semidefinite kernels via the oASIS algorithm [ 13 , 12 ] . This algorithm computes approximate eigenpairs of the kernel matrix by selecting columns from it by diagonal pivoting [ 9 ] and incrementally updating a kernel matrix approximant via the Schur complement. This often works quite well, however there exist counterexamples where diagonal pivoting fails to return an accurate approximation [ 3 ] . Moreover, the computation of the inverse matrix in the oASIS algorithm is mathematically equivalent to the computation of a pivoted partial Cholesky factorization [ 22 , p. 24] , however the direct implementation of oASIS is numerically unstable in contrast to the numerical pivoted partial Cholesky factorization. The main purpose of this paper is to combine the adaptive random sampling of the RPCholesky algorithm [ 3 ] with KDMD to address the stability problems and the drawbacks of the diagonal pivoting of the oASIS algorithm. We provide observations suggesting that the RPCholesky algorithm can lead to more stable approximations of the DMD modes when ordering the resulting DMD modes by means of data-driven residuals in the sense of [ 7 ] . We demonstrate the efficacy of the randomized KDMD algorithm and compare it to relevant competing algorithms for multiple numerical experiments. The paper is organized as follows: In Section 2 we give a short overview of the DMD algorithms relevant to this paper, focusing on how to derive data-driven residuals from the algorithm’s outputs. In Section 3 we express different options of how randomized methods can be used with KDMD, emphasizing the usage of the RPCholesky algorithm, and analyze the computational complexities of the mentioned algorithms with respect to the dimensions of the input data. Lastly, we present numerical experiments in Section 4 . 2 Fundamentals of DMD We now explain the background of DMD relevant to this paper. 2.1 SVD-Based DMD In [ 15 ] the classical SVD-based DMD algorithm was introduced. Given the data matrices X and Y\in\mathbb{C}^{N\times M} X=[x^{(1)},x^{(2)},\dots,x^{(M)}],\quad Y=[x^{(2)},x^{(3)},\dots,x^{(M+1)}], we compute the SVD X=U\Sigma V^{*} , truncate U,\Sigma and V to the numerical rank R>0 , and define K=U^{*}YV\Sigma^{\dagger}\in\mathbb{C}^{R\times R}. (1) Then, the DMD modes \xi_{i}=Uw_{i}\in\mathbb{C}^{N} computed from the right eigenpairs (\lambda_{i},w_{i}) of K span a low-dimensional subspace that captures dynamics from the data trajectory x^{(1)},x^{(2)},\dots,x^{(M)},x^{(M+1)} . To identify the dominant modes in this subspace we use the data-driven residual r(i) in the sense of [ 7 ] given by r(i)=\lVert YV\Sigma^{\dagger}w_{i}-\lambda_{i}\xi_{i}\rVert_{2} (2) and select the modes \xi_{i} with indices i minimizing the residual r(i) . 2.2 EDMD The EDMD algorithm developped in [ 20 , 10 ] is similar to the SVD-based DMD algorithm, however EDMD includes the use of (nonlinear) observables \Psi\colon\mathbb{C}^{N}\to\mathbb{C}^{1\times L} . Here, the data matrices become \Psi_{X} and \Psi_{Y}\in\mathbb{C}^{M\times L} \Psi_{X}=\begin{bmatrix}\Psi(x^{(1)})\\ \Psi(x^{(2)})\\ \vdots\\ \Psi(x^{(M)})\end{bmatrix},\quad\Psi_{Y}=\begin{bmatrix}\Psi(x^{(2)})\\ \Psi(x^{(3)})\\ \vdots\\ \Psi(x^{(M+1)})\end{bmatrix}. For the computation of the DMD modes we now define the L\times L matrix K using the SVD \Psi_{X}=U\Sigma V^{*} as K=\Psi_{X}^{\dagger}\Psi_{Y}, (3) and from the left eigenpairs (\lambda_{i},w_{i}) and the right eigenpairs (\lambda_{i},\eta_{i}) of K we compute the DMD modes \xi_{i} and the eigenfunctions \varphi_{i}(z)\in\mathbb{C} , following the derivations in [ 20 , 21 ] , by scaling w_{i}^{*}\eta_{j}=\delta_{ij} we have \xi_{i}=XV\Sigma^{\dagger}U^{*}w_{i},\quad\varphi_{i}(z)=\Psi(z)\eta_{i}, respectively. From \varphi_{i}(X)=\Psi_{X}\eta_{i}\in\mathbb{C}^{M} we obtain the reconstruction \hat{X}=\sum_{i}\xi_{i}\varphi_{i}(X)^{\top}. (4) Because of the similarities between ( 1 ) and ( 3 ), we use the analogous data-driven residual in the sense of [ 7 ] r(i)=\lVert\Psi_{Y}^{*}\xi_{i}-\lambda_{i}w_{i}\rVert_{2} to select the dominant modes and eigenfunctions. 2.3 KDMD Lastly, KDMD [ 21 ] implicitly chooses the observables \Psi by selecting a kernel function k(x,y)=\Psi(y)\Psi(x)^{*} , motivated by the kernel trick in machine learning applications [ 16 , 2 ] . With the Gramians G and A\in\mathbb{C}^{M\times M} G=k(X,X)=\Psi_{X}\Psi_{X}^{*},\quad A=k(X,Y)=\Psi_{Y}\Psi_{X}^{*} we compute the eigendecomposition G=U\Sigma^{2}U^{*} , and construct the M\times M matrix \hat{K}=\Sigma^{\dagger}U^{*}AU\Sigma^{\dagger}. (5) Again, from the left eigenpairs (\lambda_{i},w_{i}) and the right eigenpairs (\lambda_{i},\eta_{i}) of K we compute the DMD modes \xi_{i} and the eigenfunctions \varphi_{i}(z) by evaluating \displaystyle\xi_{i} \displaystyle=XU\Sigma^{\dagger}w_{i}, \displaystyle\varphi_{i}(z) \displaystyle=\Psi(z)V\eta_{i}=\Psi(z)\Psi_{X}^{*}U\Sigma^{\dagger}\eta_{i}=k(X,z)U\Sigma^{\dagger}\eta_{i}, respectively. It particularly holds that \varphi_{i}(X)=U\Sigma\eta_{i} . These eigenpairs of K from ( 3 ) and \hat{K} from ( 5 ) are related by the following statement. Lemma 1 ( [ 21 , Prop. 1] ) . Let U\Sigma V^{*} be the SVD of \Psi_{X} . Then, \lambda\neq 0 and \eta are a right eigenpair of \hat{K} from ( 5 ) if and only if \lambda and \hat{\eta}=V\eta are a right

Read the complete text