Title: Randomized Dynamic Mode Decomposition,
Abstract: This paper presents a randomized algorithm for computing the near-optimal
low-rank dynamic mode decomposition (DMD). Randomized algorithms are emerging
techniques to compute low-rank matrix approximations at a fraction of the cost
of deterministic algorithms, easing the computational challenges arising in the
area of `big data'. The idea is to derive a small matrix from the
high-dimensional data, which is then used to efficiently compute the dynamic
modes and eigenvalues. The algorithm is presented in a modular probabilistic
framework, and the approximation quality can be controlled via oversampling and
power iterations. The effectiveness of the resulting randomized DMD (rDMD)
algorithm is demonstrated on several benchmark examples of increasing
complexity, providing an accurate and efficient approach to extract
spatiotemporal coherent structures from big data in a framework that scales
with the intrinsic rank of the data, rather than the ambient measurement
dimension.