Sparse identification of non-linear dynamics

Short description: Data-driven algorithm

Sparse identification of nonlinear dynamics (SINDy) is a data-driven algorithm for obtaining dynamical systems from data. Given a series of snapshots of a dynamical system and its corresponding time derivatives, SINDy performs a sparsity-promoting regression (such as LASSO and spare Bayesian inference) on a library of nonlinear candidate functions of the snapshots against the derivatives to find the governing equations. This procedure relies on the assumption that most physical systems only have a few dominant terms which dictate the dynamics, given an appropriately selected coordinate system and quality training data. It has been applied to identify the dynamics of fluids, based on proper orthogonal decomposition, as well as other complex dynamical systems, such as biological networks.

Mathematical Overview

First, consider a dynamical system of the form

$$\dot{\text{x}}=\frac{d}{dt}\text{x}(t)=\text{f}(\text{x}(t)),$$

where $\text{x}(t)\in {\mathbb{ℝ}}^n$ is a state vector (snapshot) of the system at time $t$ and the function $\text{f}(\text{x}(t))$ defines the equations of motion and constraints of the system. The time derivative may be either prescribed or numerically approximated from the snapshots.

With $\text{x}$ and $\dot{\text{x}}$ sampled at $m$ equidistant points in time ($t_1,t_2,\cdots ,t_m$), these can be arranged into matrices of the form

$$\mathbf{𝐗}\mathbf{=}\left[\begin{array}{c}{\mathbf{𝐱}}^{\mathbf{𝐓}}\mathbf{(}{\mathbf{t}}_{\mathbf{𝟏}}\mathbf{)}\\ {\mathbf{𝐱}}^{\mathbf{𝐓}}\mathbf{(}{\mathbf{t}}_{\mathbf{𝟐}}\mathbf{)}\\ \mathbf{⋮}\\ {\mathbf{𝐱}}^{\mathbf{𝐓}}\mathbf{(}{\mathbf{t}}_{\mathbf{𝐦}}\mathbf{)}\end{array}\right]\mathbf{=}\left[\begin{array}{cccc}{\mathbf{x}}_{\mathbf{1}}\mathbf{(}{\mathbf{t}}_{\mathbf{1}}\mathbf{)}& {\mathbf{x}}_{\mathbf{2}}\mathbf{(}{\mathbf{t}}_{\mathbf{1}}\mathbf{)}& \mathbf{\cdots }& {\mathbf{x}}_{\mathbf{n}}\mathbf{(}{\mathbf{t}}_{\mathbf{1}}\mathbf{)}\\ {\mathbf{x}}_{\mathbf{1}}\mathbf{(}{\mathbf{t}}_{\mathbf{2}}\mathbf{)}& {\mathbf{x}}_{\mathbf{2}}\mathbf{(}{\mathbf{t}}_{\mathbf{2}}\mathbf{)}& \mathbf{\cdots }& {\mathbf{x}}_{\mathbf{n}}\mathbf{(}{\mathbf{t}}_{\mathbf{2}}\mathbf{)}\\ \mathbf{⋮}& \mathbf{⋮}& \mathbf{\ddots }& \mathbf{⋮}\\ {\mathbf{x}}_{\mathbf{1}}\mathbf{(}{\mathbf{t}}_{\mathbf{m}}\mathbf{)}& {\mathbf{x}}_{\mathbf{2}}\mathbf{(}{\mathbf{t}}_{\mathbf{m}}\mathbf{)}& \mathbf{\cdots }& {\mathbf{x}}_{\mathbf{n}}\mathbf{(}{\mathbf{t}}_{\mathbf{m}}\mathbf{)}\end{array}\right],$$

and similarly for $\dot{\text{X}}$.

Next, a library $\mathrm{\Theta }\mathbf{(}\text{X}\mathbf{)}$ of nonlinear candidate functions of the columns of $\text{X}$ is constructed, which may be constant, polynomial, or more exotic functions (like trigonometric and rational terms, and so on):

$$\mathrm{\Theta }\mathbf{(}\mathbf{𝐗}\mathbf{)}\mathbf{=}\left[\begin{array}{cccccccc}|& |& |& |& & |& |& \\ \mathbf{1}& \mathbf{𝐗}& {\mathbf{𝐗}}^{\mathbf{𝟐}}& {\mathbf{𝐗}}^{\mathbf{𝟑}}& \mathbf{\cdots }& \sin \mathbf{(}\mathbf{𝐗}\mathbf{)}& \cos \mathbf{(}\mathbf{𝐗}\mathbf{)}& \mathbf{\cdots }\\ |& |& |& |& & |& |& \end{array}\right]$$

The number of possible model structures from this library is combinatorically high. $\text{f}(\text{x}(t))$ is then substituted by $\mathrm{\Theta }\mathbf{(}\text{X}\mathbf{)}$ and a vector of coefficients $\mathrm{\Xi }\mathbf{=}\left[{\mathit{\xi }}_{\mathbf{𝟏}}{\mathit{\xi }}_{\mathbf{𝟐}}\mathbf{\cdots }{\mathit{\xi }}_{\mathbf{𝐧}}\right]$ determining the active terms in $\text{f}(\text{x}(t))$:

$$\dot{\mathbf{𝐗}}=\mathrm{\Theta }\mathbf{(}\mathbf{𝐗}\mathbf{)}\mathrm{\Xi }$$

Because only a few terms are expected to be active at each point in time, an assumption is made that $\text{f}(\text{x}(t))$ admits a sparse representation in $\mathrm{\Theta }\mathbf{(}\text{X}\mathbf{)}$. This then becomes an optimization problem in finding a sparse $\mathrm{\Xi }$ which optimally embeds $\dot{\text{X}}$. In other words, a parsimonious model is obtained by performing least squares regression on the system (4) with sparsity-promoting ($L_1$) regularization

$${\mathit{\xi }}_{\mathbf{𝐤}}\mathbf{=}\underset{\mathit{\xi }{\mathbf{\text{'}}}_{\mathbf{𝐤}}}{\arg \min }{\left||{\dot{\mathbf{𝐗}}}_k-\mathrm{\Theta }\mathbf{(}\mathbf{𝐗}\mathbf{)}\mathit{\xi }{\mathbf{\text{'}}}_{\mathbf{𝐤}}|\right|}_{\mathbf{𝟐}}\mathbf{+}\mathit{\lambda }{\left|\left|\mathit{\xi }{\mathbf{\text{'}}}_{\mathbf{𝐤}}\right|\right|}_{\mathbf{𝟏}},$$

where $\lambda$ is a regularization parameter. Finally, the sparse set of ${\mathit{\xi }}_{\mathbf{𝐤}}$ can be used to reconstruct the dynamical system:

$${\dot{x}}_k=\mathrm{\Theta }\mathbf{(}\mathbf{𝐱}\mathbf{)}{\mathit{\xi }}_{\mathbf{𝐤}}$$