6. VARs and DMDs#

This lecture applies computational methods that we learned about in this lecture Singular Value Decomposition to

first-order vector autoregressions (VARs)
dynamic mode decompositions (DMDs)
connections between DMDs and first-order VARs

6.1. First-Order Vector Autoregressions#

We want to fit a first-order vector autoregression

(6.1)#

X_{t + 1} = A X_{t} + C ϵ_{t + 1}, ϵ_{t + 1} ⊥ X_{t}

where $ϵ_{t + 1}$ is the time $t + 1$ component of a sequence of i.i.d. $m \times 1$ random vectors with mean vector zero and identity covariance matrix and where the $m \times 1$ vector $X_{t}$ is

(6.2)#

X_{t} = {[\begin{matrix} X_{1, t} & X_{2, t} & \dots & X_{m, t} \end{matrix}]}^{⊤}

and where $\cdot^{⊤}$ again denotes complex transposition and $X_{i, t}$ is variable $i$ at time $t$ .

We want to fit equation (6.1).

Our data are organized in an $m \times (n + 1)$ matrix $\tilde{X}$

\tilde{X} = [\begin{matrix} X_{1} ∣ X_{2} ∣ \dots ∣ X_{n} ∣ X_{n + 1} \end{matrix}]

where for $t = 1, \dots, n + 1$ , the $m \times 1$ vector $X_{t}$ is given by (6.2).

Thus, we want to estimate a system (6.1) that consists of $m$ least squares regressions of everything on one lagged value of everything.

The $i$ ’th equation of (6.1) is a regression of $X_{i, t + 1}$ on the vector $X_{t}$ .

We proceed as follows.

From $\tilde{X}$ , we form two $m \times n$ matrices

X = [\begin{matrix} X_{1} ∣ X_{2} ∣ \dots ∣ X_{n} \end{matrix}]

and

X^{'} = [\begin{matrix} X_{2} ∣ X_{3} ∣ \dots ∣ X_{n + 1} \end{matrix}]

Here $^{'}$ is part of the name of the matrix $X^{'}$ and does not indicate matrix transposition.

We use $\cdot^{⊤}$ to denote matrix transposition or its extension to complex matrices.

In forming $X$ and $X^{'}$ , we have in each case dropped a column from $\tilde{X}$ , the last column in the case of $X$ , and the first column in the case of $X^{'}$ .

Evidently, $X$ and $X^{'}$ are both $m \times n$ matrices.

We denote the rank of $X$ as $p \leq min (m, n)$ .

Two cases that interest us are

$n >> m$ , so that we have many more time series observations $n$ than variables $m$
$m >> n$ , so that we have many more variables $m$ than time series observations $n$

At a general level that includes both of these special cases, a common formula describes the least squares estimator $\hat{A}$ of $A$ .

But important details differ.

The common formula is

(6.3)#

\hat{A} = X^{'} X^{+}

where $X^{+}$ is the pseudo-inverse of $X$ .

To read about the Moore-Penrose pseudo-inverse please see Moore-Penrose pseudo-inverse

Applicable formulas for the pseudo-inverse differ for our two cases.

Short-Fat Case:

When $n >> m$ , so that we have many more time series observations $n$ than variables $m$ and when $X$ has linearly independent rows, $X X^{⊤}$ has an inverse and the pseudo-inverse $X^{+}$ is

X^{+} = X^{⊤} (X X^{⊤})^{- 1}

Here $X^{+}$ is a right-inverse that verifies $X X^{+} = I_{m \times m}$ .

In this case, our formula (6.3) for the least-squares estimator of the population matrix of regression coefficients $A$ becomes

(6.4)#

\hat{A} = X^{'} X^{⊤} (X X^{⊤})^{- 1}

This formula for least-squares regression coefficients is widely used in econometrics.

It is used to estimate vector autorgressions.

The right side of formula (6.4) is proportional to the empirical cross second moment matrix of $X_{t + 1}$ and $X_{t}$ times the inverse of the second moment matrix of $X_{t}$ .

Tall-Skinny Case:

When $m >> n$ , so that we have many more attributes $m$ than time series observations $n$ and when $X$ has linearly independent columns, $X^{⊤} X$ has an inverse and the pseudo-inverse $X^{+}$ is

X^{+} = (X^{⊤} X)^{- 1} X^{⊤}

Here $X^{+}$ is a left-inverse that verifies $X^{+} X = I_{n \times n}$ .

In this case, our formula (6.3) for a least-squares estimator of $A$ becomes

(6.5)#

\hat{A} = X^{'} (X^{⊤} X)^{- 1} X^{⊤}

Please compare formulas (6.4) and (6.5) for $\hat{A}$ .

Here we are especially interested in formula (6.5).

The $i$ th row of $\hat{A}$ is an $m \times 1$ vector of regression coefficients of $X_{i, t + 1}$ on $X_{j, t}, j = 1, \dots, m$ .

If we use formula (6.5) to calculate $\hat{A} X$ we find that

\hat{A} X = X^{'}

so that the regression equation fits perfectly.

This is a typical outcome in an underdetermined least-squares model.

To reiterate, in the tall-skinny case (described in Singular Value Decomposition) in which we have a number $n$ of observations that is small relative to the number $m$ of attributes that appear in the vector $X_{t}$ , we want to fit equation (6.1).

We confront the facts that the least squares estimator is underdetermined and that the regression equation fits perfectly.

To proceed, we’ll want efficiently to calculate the pseudo-inverse $X^{+}$ .

The pseudo-inverse $X^{+}$ will be a component of our estimator of $A$ .

As our estimator $\hat{A}$ of $A$ we want to form an $m \times m$ matrix that solves the least-squares best-fit problem

(6.6)#

\hat{A} = {argmin}_{\overset{ˇ}{A}} | | X^{'} - \overset{ˇ}{A} X | |_{F}

where $| | \cdot | |_{F}$ denotes the Frobenius (or Euclidean) norm of a matrix.

The Frobenius norm is defined as

| | A | |_{F} = \sqrt{\sum_{i = 1}^{m} \sum_{j = 1}^{m} | A_{i j} |^{2}}

The minimizer of the right side of equation (6.6) is

(6.7)#

\hat{A} = X^{'} X^{+}

where the (possibly huge) $n \times m$ matrix $X^{+} = (X^{⊤} X)^{- 1} X^{⊤}$ is again a pseudo-inverse of $X$ .

For some situations that we are interested in, $X^{⊤} X$ can be close to singular, a situation that makes some numerical algorithms be inaccurate.

To acknowledge that possibility, we’ll use efficient algorithms to constructing a reduced-rank approximation of $\hat{A}$ in formula (6.5).

Such an approximation to our vector autoregression will no longer fit perfectly.

The $i$ th row of $\hat{A}$ is an $m \times 1$ vector of regression coefficients of $X_{i, t + 1}$ on $X_{j, t}, j = 1, \dots, m$ .

An efficient way to compute the pseudo-inverse $X^{+}$ is to start with a singular value decomposition

(6.8)#

X = U Σ V^{⊤}

where we remind ourselves that for a reduced SVD, $X$ is an $m \times n$ matrix of data, $U$ is an $m \times p$ matrix, $Σ$ is a $p \times p$ matrix, and $V$ is an $n \times p$ matrix.

We can efficiently construct the pertinent pseudo-inverse $X^{+}$ by recognizing the following string of equalities.

(6.9)#

\begin{array}{r} \begin{aligned} X^{+} & = (X^{⊤} X)^{- 1} X^{⊤} \\ = (V Σ U^{⊤} U Σ V^{⊤})^{- 1} V Σ U^{⊤} \\ = (V Σ Σ V^{⊤})^{- 1} V Σ U^{⊤} \\ = V Σ^{- 1} Σ^{- 1} V^{⊤} V Σ U^{⊤} \\ = V Σ^{- 1} U^{⊤} \end{aligned} \end{array}

(Since we are in the $m >> n$ case in which $V^{⊤} V = I_{p \times p}$ in a reduced SVD, we can use the preceding string of equalities for a reduced SVD as well as for a full SVD.)

Thus, we shall construct a pseudo-inverse $X^{+}$ of $X$ by using a singular value decomposition of $X$ in equation (6.8) to compute

(6.10)#

X^{+} = V Σ^{- 1} U^{⊤}

where the matrix $Σ^{- 1}$ is constructed by replacing each non-zero element of $Σ$ with $σ_{j}^{- 1}$ .

We can use formula (6.10) together with formula (6.7) to compute the matrix $\hat{A}$ of regression coefficients.

Thus, our estimator $\hat{A} = X^{'} X^{+}$ of the $m \times m$ matrix of coefficients $A$ is

(6.11)#

\hat{A} = X^{'} V Σ^{- 1} U^{⊤}

6.2. Dynamic Mode Decomposition (DMD)#

We turn to the $m >> n$ tall and skinny case associated with Dynamic Mode Decomposition.

Here an $m \times n + 1$ data matrix $\tilde{X}$ contains many more attributes (or variables) $m$ than time periods $n + 1$ .

Dynamic mode decomposition was introduced by [Schmid, 2010],

You can read about Dynamic Mode Decomposition [Kutz et al., 2016] and [Brunton and Kutz, 2019] (section 7.2).

Dynamic Mode Decomposition (DMD) computes a rank $r < p$ approximation to the least squares regression coefficients $\hat{A}$ described by formula (6.11).

We’ll build up gradually to a formulation that is useful in applications.

We’ll do this by describing three alternative representations of our first-order linear dynamic system, i.e., our vector autoregression.

Guide to three representations: In practice, we’ll mainly be interested in Representation 3.

We use the first two representations to present some useful intermediate steps that help us to appreciate what is under the hood of Representation 3.

In applications, we’ll use only a small subset of DMD modes to approximate dynamics.

We use such a small subset of DMD modes to construct a reduced-rank approximation to $A$ .

To do that, we’ll want to use the reduced SVD’s affiliated with representation 3, not the full SVD’s affiliated with representations 1 and 2.

Guide to impatient reader: In our applications, we’ll be using Representation 3.

You might want to skip the stage-setting representations 1 and 2 on first reading.

6.3. Representation 1#

In this representation, we shall use a full SVD of $X$ .

We use the $m$ columns of $U$ , and thus the $m$ rows of $U^{⊤}$ , to define a $m \times 1$ vector ${\tilde{b}}_{t}$ as

(6.12)#

{\tilde{b}}_{t} = U^{⊤} X_{t} .

The original data $X_{t}$ can be represented as

(6.13)#

X_{t} = U {\tilde{b}}_{t}

(Here we use $b$ to remind ourselves that we are creating a basis vector.)

Since we are now using a full SVD, $U U^{⊤} = I_{m \times m}$ .

So it follows from equation (6.12) that we can reconstruct $X_{t}$ from ${\tilde{b}}_{t}$ .

In particular,

Equation (6.12) serves as an encoder that rotates the $m \times 1$ vector $X_{t}$ to become an $m \times 1$ vector ${\tilde{b}}_{t}$
Equation (6.13) serves as a decoder that reconstructs the $m \times 1$ vector $X_{t}$ by rotating the $m \times 1$ vector ${\tilde{b}}_{t}$

Define a transition matrix for an $m \times 1$ basis vector ${\tilde{b}}_{t}$ by

(6.14)#

\tilde{A} = U^{⊤} \hat{A} U

We can recover $\hat{A}$ from

\hat{A} = U \tilde{A} U^{⊤}

Dynamics of the $m \times 1$ basis vector ${\tilde{b}}_{t}$ are governed by

{\tilde{b}}_{t + 1} = \tilde{A} {\tilde{b}}_{t}

To construct forecasts ${\overset{―}{X}}_{t}$ of future values of $X_{t}$ conditional on $X_{1}$ , we can apply decoders (i.e., rotators) to both sides of this equation and deduce

{\overset{―}{X}}_{t + 1} = U {\tilde{A}}^{t} U^{⊤} X_{1}

where we use ${\overset{―}{X}}_{t + 1}, t \geq 1$ to denote a forecast.

6.4. Representation 2#

This representation is related to one originally proposed by [Schmid, 2010].

It can be regarded as an intermediate step on the way to obtaining a related representation 3 to be presented later

As with Representation 1, we continue to

use a full SVD and not a reduced SVD

As we observed and illustrated in a lecture about the Singular Value Decomposition

(a) for a full SVD $U U^{⊤} = I_{m \times m}$ and $U^{⊤} U = I_{p \times p}$ are both identity matrices
(b) for a reduced SVD of $X$ , $U^{⊤} U$ is not an identity matrix.

As we shall see later, a full SVD is too confining for what we ultimately want to do, namely, cope with situations in which $U^{⊤} U$ is not an identity matrix because we use a reduced SVD of $X$ .

But for now, let’s proceed under the assumption that we are using a full SVD so that requirements (a) and (b) are both satisfied.

Form an eigendecomposition of the $m \times m$ matrix $\tilde{A} = U^{⊤} \hat{A} U$ defined in equation (6.14):

(6.15)#

\tilde{A} = W Λ W^{- 1}

where $Λ$ is a diagonal matrix of eigenvalues and $W$ is an $m \times m$ matrix whose columns are eigenvectors corresponding to rows (eigenvalues) in $Λ$ .

When $U U^{⊤} = I_{m \times m}$ , as is true with a full SVD of $X$ , it follows that

(6.16)#

\hat{A} = U \tilde{A} U^{⊤} = U W Λ W^{- 1} U^{⊤}

According to equation (6.16), the diagonal matrix $Λ$ contains eigenvalues of $\hat{A}$ and corresponding eigenvectors of $\hat{A}$ are columns of the matrix $U W$ .

It follows that the systematic (i.e., not random) parts of the $X_{t}$ dynamics captured by our first-order vector autoregressions are described by

X_{t + 1} = U W Λ W^{- 1} U^{⊤} X_{t}

Multiplying both sides of the above equation by $W^{- 1} U^{⊤}$ gives

W^{- 1} U^{⊤} X_{t + 1} = Λ W^{- 1} U^{⊤} X_{t}

{\hat{b}}_{t + 1} = Λ {\hat{b}}_{t}

where our encoder is

{\hat{b}}_{t} = W^{- 1} U^{⊤} X_{t}

and our decoder is

X_{t} = U W {\hat{b}}_{t}

We can use this representation to construct a predictor ${\overset{―}{X}}_{t + 1}$ of $X_{t + 1}$ conditional on $X_{1}$ via:

(6.17)#

{\overset{―}{X}}_{t + 1} = U W Λ^{t} W^{- 1} U^{⊤} X_{1}

In effect, [Schmid, 2010] defined an $m \times m$ matrix $Φ_{s}$ as

(6.18)#

Φ_{s} = U W

and a generalized inverse

(6.19)#

Φ_{s}^{+} = W^{- 1} U^{⊤}

[Schmid, 2010] then represented equation (6.17) as

(6.20)#

{\overset{―}{X}}_{t + 1} = Φ_{s} Λ^{t} Φ_{s}^{+} X_{1}

Components of the basis vector ${\hat{b}}_{t} = W^{- 1} U^{⊤} X_{t} \equiv Φ_{s}^{+} X_{t}$ are
DMD projected modes.

To understand why they are called projected modes, notice that

Φ_{s}^{+} = (Φ_{s}^{⊤} Φ_{s})^{- 1} Φ_{s}^{⊤}

so that the $m \times p$ matrix

\hat{b} = Φ_{s}^{+} X

is a matrix of regression coefficients of the $m \times n$ matrix $X$ on the $m \times p$ matrix $Φ_{s}$ .

We’ll say more about this interpretation in a related context when we discuss representation 3, which was suggested by Tu et al. [Tu et al., 2014].

It is more appropriate to use representation 3 when, as is often the case in practice, we want to use a reduced SVD.

6.5. Representation 3#

Departing from the procedures used to construct Representations 1 and 2, each of which deployed a full SVD, we now use a reduced SVD.

Again, we let $p \leq min (m, n)$ be the rank of $X$ .

Construct a reduced SVD

X = \tilde{U} \tilde{Σ} {\tilde{V}}^{⊤},

where now $\tilde{U}$ is $m \times p$ , $\tilde{Σ}$ is $p \times p$ , and ${\tilde{V}}^{⊤}$ is $p \times n$ .

Our minimum-norm least-squares approximator of $A$ now has representation

(6.21)#

\hat{A} = X^{'} \tilde{V} {\tilde{Σ}}^{- 1} {\tilde{U}}^{⊤}

Computing Dominant Eigenvectors of $\hat{A}$

We begin by paralleling a step used to construct Representation 1, define a transition matrix for a rotated $p \times 1$ state ${\tilde{b}}_{t}$ by

(6.22)#

\tilde{A} = {\tilde{U}}^{⊤} \hat{A} \tilde{U}

Interpretation as projection coefficients

[Brunton and Kutz, 2022] remark that $\tilde{A}$ can be interpreted in terms of a projection of $\hat{A}$ onto the $p$ modes in $\tilde{U}$ .

To verify this, first note that, because ${\tilde{U}}^{⊤} \tilde{U} = I$ , it follows that

(6.23)#

\tilde{A} = {\tilde{U}}^{⊤} \hat{A} \tilde{U} = {\tilde{U}}^{⊤} X^{'} \tilde{V} {\tilde{Σ}}^{- 1} {\tilde{U}}^{⊤} \tilde{U} = {\tilde{U}}^{⊤} X^{'} \tilde{V} {\tilde{Σ}}^{- 1} {\tilde{U}}^{⊤}

Next, we’ll just compute the regression coefficients in a projection of $\hat{A}$ on $\tilde{U}$ using a standard least-squares formula

({\tilde{U}}^{⊤} \tilde{U})^{- 1} {\tilde{U}}^{⊤} \hat{A} = ({\tilde{U}}^{⊤} \tilde{U})^{- 1} {\tilde{U}}^{⊤} X^{'} \tilde{V} {\tilde{Σ}}^{- 1} {\tilde{U}}^{⊤} = {\tilde{U}}^{⊤} X^{'} \tilde{V} {\tilde{Σ}}^{- 1} {\tilde{U}}^{⊤} = \tilde{A} .

Thus, we have verified that $\tilde{A}$ is a least-squares projection of $\hat{A}$ onto $\tilde{U}$ .

An Inverse Challenge

Because we are using a reduced SVD, $\tilde{U} {\tilde{U}}^{⊤} \neq I$ .

Consequently,

\hat{A} \neq \tilde{U} \tilde{A} {\tilde{U}}^{⊤},

so we can’t simply recover $\hat{A}$ from $\tilde{A}$ and $\tilde{U}$ .

A Blind Alley

We can start by hoping for the best and proceeding to construct an eigendecomposition of the $p \times p$ matrix $\tilde{A}$ :

(6.24)#

\tilde{A} = \tilde{W} Λ {\tilde{W}}^{- 1}

where $Λ$ is a diagonal matrix of $p$ eigenvalues and the columns of $\tilde{W}$ are corresponding eigenvectors.

Mimicking our procedure in Representation 2, we cross our fingers and compute an $m \times p$ matrix

(6.25)#

{\tilde{Φ}}_{s} = \tilde{U} \tilde{W}

that corresponds to (6.18) for a full SVD.

At this point, where $\hat{A}$ is given by formula (6.21) it is interesting to compute $\hat{A} {\tilde{Φ}}_{s}$ :

\begin{array}{r} \begin{aligned} \hat{A} {\tilde{Φ}}_{s} & = (X^{'} \tilde{V} {\tilde{Σ}}^{- 1} {\tilde{U}}^{⊤}) (\tilde{U} \tilde{W}) \\ = X^{'} \tilde{V} {\tilde{Σ}}^{- 1} \tilde{W} \\ \neq (\tilde{U} \tilde{W}) Λ \\ = {\tilde{Φ}}_{s} Λ \end{aligned} \end{array}

That $\hat{A} {\tilde{Φ}}_{s} \neq {\tilde{Φ}}_{s} Λ$ means that, unlike the corresponding situation in Representation 2, columns of ${\tilde{Φ}}_{s} = \tilde{U} \tilde{W}$ are not eigenvectors of $\hat{A}$ corresponding to eigenvalues on the diagonal of matix $Λ$ .

An Approach That Works

Continuing our quest for eigenvectors of $\hat{A}$ that we can compute with a reduced SVD, let’s define an $m \times p$ matrix $Φ$ as

(6.26)#

Φ \equiv \hat{A} {\tilde{Φ}}_{s} = X^{'} \tilde{V} {\tilde{Σ}}^{- 1} \tilde{W}

It turns out that columns of $Φ$ are eigenvectors of $\hat{A}$ .

This is a consequence of a result established by Tu et al. [Tu et al., 2014] that we now present.

Proposition The $p$ columns of $Φ$ are eigenvectors of $\hat{A}$ .

Proof: From formula (6.26) we have

\begin{aligned} \hat{A} Φ & = (X^{'} \tilde{V} {\tilde{Σ}}^{- 1} {\tilde{U}}^{⊤}) (X^{'} \tilde{V} Σ^{- 1} \tilde{W}) \\ = X^{'} \tilde{V} {\tilde{Σ}}^{- 1} \tilde{A} \tilde{W} \\ = X^{'} \tilde{V} {\tilde{Σ}}^{- 1} \tilde{W} Λ \\ = Φ Λ \end{aligned}

so that

(6.27)#

\hat{A} Φ = Φ Λ .

Let $ϕ_{i}$ be the $i$ th column of $Φ$ and $λ_{i}$ be the corresponding $i$ eigenvalue of $\tilde{A}$ from decomposition (6.24).

Equating the $m \times 1$ vectors that appear on the two sides of equation (6.27) gives

\hat{A} ϕ_{i} = λ_{i} ϕ_{i} .

This equation confirms that $ϕ_{i}$ is an eigenvector of $\hat{A}$ that corresponds to eigenvalue $λ_{i}$ of both $\tilde{A}$ and $\hat{A}$ .

This concludes the proof.

Also see [Brunton and Kutz, 2022] (p. 238)

6.5.1. Decoder of $\overset{ˇ}{b}$ as a linear projection#

From eigendecomposition (6.27) we can represent $\hat{A}$ as

(6.28)#

\hat{A} = Φ Λ Φ^{+} .

From formula (6.28) we can deduce dynamics of the $p \times 1$ vector ${\overset{ˇ}{b}}_{t}$ :

{\overset{ˇ}{b}}_{t + 1} = Λ {\overset{ˇ}{b}}_{t}

where

(6.29)#

{\overset{ˇ}{b}}_{t} = Φ^{+} X_{t}

Since the $m \times p$ matrix $Φ$ has $p$ linearly independent columns, the generalized inverse of $Φ$ is

Φ^{+} = (Φ^{⊤} Φ)^{- 1} Φ^{⊤}

and so

(6.30)#

\overset{ˇ}{b} = (Φ^{⊤} Φ)^{- 1} Φ^{⊤} X

The $p \times n$ matrix $\overset{ˇ}{b}$ is recognizable as a matrix of least squares regression coefficients of the $m \times n$ matrix $X$ on the $m \times p$ matrix $Φ$ and consequently

(6.31)#

\overset{ˇ}{X} = Φ \overset{ˇ}{b}

is an $m \times n$ matrix of least squares projections of $X$ on $Φ$ .

Variance Decomposition of $X$

By virtue of the least-squares projection theory discussed in this quantecon lecture https://python-advanced.quantecon.org/orth_proj.html, we can represent $X$ as the sum of the projection $\overset{ˇ}{X}$ of $X$ on $Φ$ plus a matrix of errors.

To verify this, note that the least squares projection $\overset{ˇ}{X}$ is related to $X$ by

X = \overset{ˇ}{X} + ϵ

(6.32)#

X = Φ \overset{ˇ}{b} + ϵ

where $ϵ$ is an $m \times n$ matrix of least squares errors satisfying the least squares orthogonality conditions $ϵ^{⊤} Φ = 0$ or

(6.33)#

(X - Φ \overset{ˇ}{b})^{⊤} Φ = 0_{m \times p}

Rearranging the orthogonality conditions (6.33) gives $X^{⊤} Φ = \overset{ˇ}{b} Φ^{⊤} Φ$ , which implies formula (6.30).

6.5.2. An Approximation#

We now describe a way to approximate the $p \times 1$ vector ${\overset{ˇ}{b}}_{t}$ instead of using formula (6.29).

In particular, the following argument adapted from [Brunton and Kutz, 2022] (page 240) provides a computationally efficient way to approximate ${\overset{ˇ}{b}}_{t}$ .

For convenience, we’ll apply the method at time $t = 1$ .

For $t = 1$ , from equation (6.32) we have

(6.34)#

{\overset{ˇ}{X}}_{1} = Φ {\overset{ˇ}{b}}_{1}

where ${\overset{ˇ}{b}}_{1}$ is a $p \times 1$ vector.

Recall from representation 1 above that $X_{1} = U {\tilde{b}}_{1}$ , where ${\tilde{b}}_{1}$ is a time $1$ basis vector for representation 1 and $U$ is from the full SVD $X = U Σ V^{⊤}$ .

It then follows from equation (6.32) that

U {\tilde{b}}_{1} = X^{'} \tilde{V} {\tilde{Σ}}^{- 1} \tilde{W} {\overset{ˇ}{b}}_{1} + ϵ_{1}

where $ϵ_{1}$ is a least-squares error vector from equation (6.32).

It follows that

{\tilde{b}}_{1} = U^{⊤} X^{'} V {\tilde{Σ}}^{- 1} \tilde{W} {\overset{ˇ}{b}}_{1} + U^{⊤} ϵ_{1}

Replacing the error term $U^{⊤} ϵ_{1}$ by zero, and replacing $U$ from a full SVD of $X$ with $\tilde{U}$ from a reduced SVD, we obtain an approximation ${\hat{b}}_{1}$ to ${\tilde{b}}_{1}$ :

{\hat{b}}_{1} = {\tilde{U}}^{⊤} X^{'} \tilde{V} {\tilde{Σ}}^{- 1} \tilde{W} {\overset{ˇ}{b}}_{1}

Recall that from equation (6.23), $\tilde{A} = {\tilde{U}}^{⊤} X^{'} \tilde{V} {\tilde{Σ}}^{- 1}$ .

It then follows that

{\hat{b}}_{1} = \tilde{A} \tilde{W} {\overset{ˇ}{b}}_{1}

and therefore, by the eigendecomposition (6.24) of $\tilde{A}$ , we have

{\hat{b}}_{1} = \tilde{W} Λ {\overset{ˇ}{b}}_{1}

Consequently,

{\hat{b}}_{1} = (\tilde{W} Λ)^{- 1} {\tilde{b}}_{1}

(6.35)#

{\hat{b}}_{1} = (\tilde{W} Λ)^{- 1} {\tilde{U}}^{⊤} X_{1},

which is a computationally efficient approximation to the following instance of equation (6.29) for the initial vector ${\overset{ˇ}{b}}_{1}$ :

(6.36)#

{\overset{ˇ}{b}}_{1} = Φ^{+} X_{1}

(To highlight that (6.35) is an approximation, users of DMD sometimes call components of basis vector ${\overset{ˇ}{b}}_{t} = Φ^{+} X_{t}$ the exact DMD modes and components of ${\hat{b}}_{t} = (\tilde{W} Λ)^{- 1} {\tilde{U}}^{⊤} X_{t}$ the approximate modes.)

Conditional on $X_{t}$ , we can compute a decoded ${\overset{ˇ}{X}}_{t + j}, j = 1, 2, \dots$ from the exact modes via

(6.37)#

{\overset{ˇ}{X}}_{t + j} = Φ Λ^{j} Φ^{+} X_{t}

or use compute a decoded ${\hat{X}}_{t + j}$ from approximate modes via

(6.38)#

{\hat{X}}_{t + j} = Φ Λ^{j} (\tilde{W} Λ)^{- 1} {\tilde{U}}^{⊤} X_{t} .

We can then use a decoded ${\overset{ˇ}{X}}_{t + j}$ or ${\hat{X}}_{t + j}$ to forecast $X_{t + j}$ .

6.5.3. Using Fewer Modes#

In applications, we’ll actually use only a few modes, often three or less.

Some of the preceding formulas assume that we have retained all $p$ modes associated with singular values of $X$ .

We can adjust our formulas to describe a situation in which we instead retain only the $r < p$ largest singular values.

In that case, we simply replace $\tilde{Σ}$ with the appropriate $r \times r$ matrix of singular values, $\tilde{U}$ with the $m \times r$ matrix whose columns correspond to the $r$ largest singular values, and $\tilde{V}$ with the $n \times r$ matrix whose columns correspond to the $r$ largest singular values.

Counterparts of all of the salient formulas above then apply.

6.6. Source for Some Python Code#

You can find a Python implementation of DMD here:

https://mathlab.sissa.it/pydmd