Randomized Structured Total-Least-Squares-Based Higher-Order Extended Dynamic Mode Decomposition

Abstract. Dynamic mode decomposition (DMD), a fundamental methodology for data-driven dynamical systems analysis, faces three persistent limitations: restricted applicability to nonlinear systems, sensitivity to noise-induced instabilities, and computational inefficiency at scale. Recent advances partially address these constraints. However, these approaches still require a trade-off between computational efficiency and accuracy. This work introduces a unified randomized higher-order extended DMD (randomized HOEDMD) framework integrating randomized linear algebra with structured total least squares. Its innovations include Cholesky decomposition-enhanced randomized QB algorithms that reduce spatial complexity. Furthermore, we establish theoretical error bounds demonstrating quantifiable convergence to deterministic HOEDMD solutions under mild conditions. Evaluations across synthetic, cylinder wake flow, and functional magnetic resonance imaging (fMRI) datasets demonstrate (1) substantially improved computational efficiency while maintaining accuracy relative to the deterministic counterpart, and (2) superior precision compared to standard DMD and its randomized variants. Quantitatively, on the cylinder wake flow benchmark our method delivers [Formula: see text]42[Formula: see text] speedup at matched spectral accuracy; on large-scale voxel-level fMRI it avoids out-of-memory and completes in [Formula: see text]2.6 s. Overall, the proposed method provides an efficient, theoretically grounded approach for analyzing noise-contaminated, multiscale dynamical systems, effectively bridging computational tractability and dynamical fidelity.