Dynamic mode decomposition

Dynamic mode decomposition (DMD) is a dimensionality reduction algorithm developed by Peter Schmid in 2008.
Given a time series of data, DMD computes a set of modes each of which is associated with a fixed oscillation frequency and decay/growth rate. For linear systems in particular, these modes and frequencies are analogous to the normal modes of the system, but more generally, they are approximations of the modes and eigenvalues of the composition operator (also called the Koopman operator). Due to the intrinsic temporal behaviors associated with each mode, DMD differs from dimensionality reduction methods such as principal component analysis, which computes orthogonal modes that lack predetermined temporal behaviors. Because its modes are not orthogonal, DMD-based representations can be less parsimonious than those generated by PCA. However, they can also be more physically meaningful because each mode is associated with a damped (or driven) sinusoidal behavior in time.
Overview.
Dynamic mode decomposition was first introduced by Schmid as a numerical procedure for extracting dynamical features from flow data.
The data takes the form of a snapshot sequence 
where formula_2 is the formula_3-th snapshot of the flow field, and formula_4 is a data matrix whose columns are the individual snapshots. The subscript and superscript denote the index of the snapshot in the first and last columns respectively. These snapshots are assumed to be related via a linear mapping that defines a linear dynamical system
that remains approximately the same over the duration of the sampling period. Written in matrix form, this implies that 
where formula_7 is the vector of residuals that accounts for behaviors that cannot be described completely by formula_8, formula_9, formula_10, and formula_11. Regardless of the approach, the output of DMD is the eigenvalues and eigenvectors of formula_8, which are referred to as the "DMD eigenvalues" and "DMD modes" respectively.
Algorithm.
There are two methods for obtaining these eigenvalues and modes. The first is Arnoldi-like, which is useful for theoretical analysis due to its connection with Krylov methods. The second is a singular value decomposition (SVD) based approach that is more robust to noise in the data and to numerical errors.
The Arnoldi approach.
In fluids applications, the size of a snapshot, formula_13, is assumed to be much larger than the number of snapshots formula_14, so there are many equally valid choices of formula_8. The original DMD algorithm picks formula_8 so that each of the snapshots in formula_17 can be written as the linear combination of the snapshots in formula_18.
Because most of the snapshots appear in both data sets, this representation is error free for all snapshots except formula_19, which is written as 
where formula_21 is a set of coefficients DMD must identify and formula_7 is the residual.
In total, 
where formula_24 is the companion matrix
The vector formula_26 can be computed by solving a least squares problem, which minimizes the overall residual. In particular if we take the QR decomposition of formula_27, then formula_28.
In this form, DMD is a type of Arnoldi method, and therefore the eigenvalues of formula_24 are approximations of the eigenvalues of formula_8. Furthermore, if formula_31 is an eigenvector of formula_24, then formula_33 is an approximate eigenvector of formula_8. The reason an eigendecomposition is performed on formula_24 rather than formula_8 is because formula_24 is much smaller than formula_8, so the computational cost of DMD is determined by the number of snapshots rather than the size of a snapshot.
The SVD-based approach.
Instead of computing the companion matrix formula_39, the SVD-based approach yields the matrix formula_40 that is related to formula_8 via a similarity transform. To do this, assume we have the SVD of formula_42. Then 
Equivalent to the assumption made by the Arnoldi-based approach, we choose formula_8 such that the snapshots in formula_17 can be written as the linear superposition of the columns in formula_46, which is equivalent to requiring that they can be written as the superposition of POD modes. With this restriction, minimizing the residual requires that it is orthogonal to the POD basis (i.e., formula_47). Then multiplying both sides of the equation above by formula_48 yields formula_49, which can be manipulated to obtain
Because formula_8 and formula_40 are related via similarity transform, the eigenvalues of formula_24 are the eigenvalues of formula_8, and if formula_31 is an eigenvector of formula_40, then formula_57 is an eigenvector of formula_8.
In summary, the SVD-based approach is as follows:
The advantage of the SVD-based approach over the Arnoldi-like approach is that noise in the data and numerical truncation issues can be compensated for by truncating the SVD of formula_18. As noted in accurately computing more than the first couple modes and eigenvalues can be difficult on experimental data sets without this truncation step.
Theoretical and algorithmic advancements.
Since its inception in 2010, a considerable amount of work has focused on understanding and improving DMD. One of the first analyses of DMD by Rowley et al. established the connection between DMD and the Koopman operator, and helped to explain the output of DMD when applied to nonlinear systems. Since then, a number of modifications have been developed that either strengthen this connection further or enhance the robustness and applicability of the approach.
In addition to the algorithms listed here, similar application-specific techniques have been developed. For example, like DMD, Prony's method represents a signal as the superposition of damped sinusoids. In climate science, linear inverse modeling is also strongly connected with DMD. For a more comprehensive list, see Tu et al.
Examples.
Trailing edge of a profile.
The wake of an obstacle in the flow may develop a Kármán vortex street. The Fig.1 shows the shedding of a vortex behind the trailing edge of a profile. The DMD-analysis was applied to 90 sequential Entropy fields and yield an approximated eigenvalue-spectrum as depicted below. The analysis was applied to the numerical results, without referring to the governing equations. The profile is seen in white. The white arcs are the processor boundaries since the computation was performed on a parallel computer using different computational blocks.
Roughly a third of the spectrum was highly damped (large, negative formula_73) and is not shown. The dominant shedding mode is shown in the following pictures. The image to the left is the real part, the image to the right, the imaginary part of the eigenvector.
Again, the entropy-eigenvector is shown in this picture. The acoustic contents of the same mode is seen in the bottom half of the next plot. The top half corresponds to the entropy mode as above.
Synthetic example of a traveling pattern.
The DMD analysis assumes a pattern of the form
formula_74
where formula_75 is any of the independent variables of the problem, but has to be selected in advance.
Take for example the pattern
With the time as the preselected exponential factor.
A sample is given in the following figure with formula_77, formula_78 and formula_79. The left picture shows the pattern without, the right with noise added. The amplitude of the random noise is the same as that of the pattern.
A DMD analysis is performed with 21 synthetically generated fields using a time interval formula_80, limiting the analysis to formula_81.
The spectrum is symmetric and shows three almost undamped modes (small negative real part), whereas the other modes are heavily damped.
Their numerical values are formula_82 respectively. The real one corresponds to the mean of the field, whereas formula_83 corresponds to the imposed pattern with formula_84. Yielding a relative error of −1/1000. Increasing the noise to 10 times the signal value yields about the same error. The real and imaginary part of one of the latter two eigenmodes is depicted in the following figure.
See also.
Several other decompositions of experimental data exist. If the governing equations are available, an eigenvalue decomposition might be feasible.