(470g) Unifying Theorems for Subspace Identification and Dynamic Mode Decomposition

We present a theoretical treatment that unifies two data-driven dynamic model identification techniques: subspace ID (SID) and dynamic mode decomposition (DMD).

SID seeks to identify a dynamical model in state-space form from output sequence data [1,2]. SID adopts a sequential approach: first, an extended observability matrix and the state sequence are identified from the output data; then these quantities are used to identify the state-space system matrices. Various SID algorithms have been proposed in the literature such as PC, UPC, and CVA [3] (for autonomous systems) and N4SID [4], MOSEP [5], and CVA [6] (for non-autonomous systems). In seminal work, Van Overschee and De Moor [7] have shown that the only defining feature of such methods is the weighting scheme used for singular value decomposition (SVD); thus, even if there exist different variants of SID algorithms, they are not significantly different from each other. SID techniques have been the dominant paradigm for state-space dynamic model identification in industrial applications [2,8].

DMD is an identification method that has recently gained considerable attention in the literature as an identification method to deal with high-dimensional data (as those arising in computational fluid dynamics) [9,10,11]. In DMD, a low-rank dynamical model is obtained by approximately solving a linear regression problem via truncated SVD. Subsequently, an alternative rank-constrained regression approach, which has optimality guarantees, has been proposed [12]. Connections between DMD and classical Koopman operator theory have also been established in [9,10,13]. Unlike SID, however, the model order of DMD is assumed to be equal to the order of a delay-embedded observable (i.e., low-order state space is not formally constructed); as such, DMD models do not provide a direct low-order state-space representation.

In this work, we present unifying theorems for SID and DMD for autonomous dynamical systems [14]. Connections between SID and DMD have only been addressed superficially in the literature (e.g., see [15,16]). We observe that SID seeks to solve an optimization problem to estimate an extended observability matrix and a state sequence that minimizes the prediction error for the state-space model. In addition, we observe that DMD seeks to solve a rank-constrained matrix regression problem that minimizes the prediction error of an extended autoregressive model. We prove that existence conditions for perfect (error-free) state-space and low-rank extended autoregressive models are equivalent and that the SID and DMD optimization problems are equivalent; therefore, SID and DMD fundamentally solves the same problem. We exploit these results to propose an SID-DMD algorithm that delivers a provably optimal model and that is easy to implement. In specific, in the proposed algorithm, we first solve a low-rank linear regression problem with a delay-embedded data set, and then directly extract the low-order system matrices from the factorization of the identified low-rank model. The optimality guarantees of the identified models are provided. We demonstrate our developments using a case study that aims to build dynamical models directly from pixel (video) data.

References:

[1] Van Overschee, Peter, and B. L. De Moor. Subspace identification for linear systems: Theory—Implementation—Applications. Springer Science & Business Media, 2012.
[2] Qin, S. Joe. "An overview of subspace identification." Computers & chemical engineering 30.10-12 (2006): 1502-1513.
[3] Arun, K. S., and S. Y. Kung. "Balanced approximation of stochastic systems." SIAM journal on matrix analysis and applications 11.1 (1990): 42-68.
[4] Van Overschee, Peter, and Bart De Moor. "N4SID: Subspace algorithms for the identification of combined deterministic-stochastic systems." Automatica 30.1 (1994): 75-93.
[5] Verhaegen, Michel. "Identification of the deterministic part of MIMO state space models given in innovations form from input-output data." Automatica 30.1 (1994): 61-74.
[6] Larimore, Wallace E. "Canonical variate analysis in identification, filtering, and adaptive control." 29th IEEE Conference on Decision and control. IEEE, 1990.
[7] Van Overschee, Peter, and Bart De Moor. "A unifying theorem for three subspace system identification algorithms." Automatica 31.12 (1995): 1853-1864.
[8] Favoreel, Wouter, Bart De Moor, and Peter Van Overschee. "Subspace state space system identification for industrial processes." Journal of process control 10.2-3 (2000): 149-155.
[9] Schmid, Peter J. "Dynamic mode decomposition of numerical and experimental data." Journal of fluid mechanics 656 (2010): 5-28.
[10] Tu, Jonathan H., et al. "On dynamic mode decomposition: Theory and applications." Journal of Computational Dynamics 1.2 (2014): 391-421.
[11] Kutz, J. Nathan, et al. Dynamic mode decomposition: data-driven modeling of complex systems. Society for Industrial and Applied Mathematics, 2016.
[12] Héas, Patrick, and Cédric Herzet. "Optimal low-rank dynamic mode decomposition." 2017 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE, 2017.
[13] Lasota, Andrzej, and Michael C. Mackey. Chaos, fractals, and noise: stochastic aspects of dynamics. Vol. 97. Springer Science & Business Media, 2013.
[14] Shin, Sungho, Qiugang Lu, and Victor M. Zavala. "Unifying Theorems for Subspace Identification and Dynamic Mode Decomposition." arXiv preprint arXiv:2003.07410 (2020).
[15] Proctor, Joshua L., Steven L. Brunton, and J. Nathan Kutz. "Dynamic mode decomposition with control." SIAM Journal on Applied Dynamical Systems 15.1 (2016): 142-161.
[16] Arbabi, Hassan, and Igor Mezic. "Ergodic theory, dynamic mode decomposition, and computation of spectral properties of the Koopman operator." SIAM Journal on Applied Dynamical Systems 16.4 (2017): 2096-2126.