Learning Koopman Invariant Subspaces
for Dynamic Mode Decomposition

Naoya Takeishi (The University of Tokyo),
Yoshinobu Kawahara (Osaka University / RIKEN AIP),
Takehisa Yairi (The University of Tokyo)
IBIS 2018 in Tokyo, November 2017
To appear in NIPS 2017.
preprint: https://arxiv.org/abs/1710.04340

BackgroundMotivation: Analysis of Dynamical Systems• In physics, biology, etc., a wide variety of complex phenomena aredescribed in terms of dynamical systems.
• In machine learning, state space models are utilized classically.
xt+1 = f (xt ),x ∈ M (state space)/ Challenging to know (a part of) properties of nonlinear f .
1 / 11

Background: Operator-theoretic view of nonlinear dynamics• Fundamental idea: Lift nonlinear system to linear regime by K.
Definition (Koopman operator [Koopman ’31, Mezić ’05])
Let g : M → C be an observable. Koopman operator K is an infinite
dimensional linear operator that describes time-evolution of g, i.e.,g(f (x)) = Kg(x),g ∈ G (function space), Benefit: control, modal decomposition (→ next page), etc.

2 / 11

Modal decomposition based on spectra of K

• Consider eigenvalues λ and eigenfunctions ϕ of K:
K ϕi (x) = λi ϕi (x)fori = 1, 2, . . . , ∞.

• For simplicity, assume K has only discrete spectrum (eigenvalues).
• Project g(·) to span{ϕ1 (·), ϕ2 (·), . . . } → Koopman modes
g(x) =∞Xϕi (x) vi

i=1• Applying K to both sides for t times, we have g(xt )’s decomposition
into quasi-periodic modes (Koopman mode decomposition, KMD):

g(xt ) =∞Xi=1(λti ϕi (x0 )vi ,| {z }wiwhere|λi |decay rate of wi ,∠λifrequency of wi .
3 / 11

Application examples• fluid mechanics [many], robotics [Berger+ ’15], neuroscience [Brunton+ ’16],
epidemiology [Proctor&Eckhoff ’15], finance [Mann&Kutz ’16], medical care
[Bourantas+ ’16], building systems [Georgescu+ ’12], power systems [Raak+ ’16,Susuki+ ’16], image processing [Kutz+ ’16], control [Mauroy&Goncalves ’16], etc.

4 / 11

How to compute modal decomposition by Koopman operator?

• KMD can be computed using dynamic mode decomposition (DMD)[Rowley+ ’09, Schmid 10, etc.] if the assumption below is satisfied.
II

DMD just computes eigendecomposition of A, where yt+1 ≈ Ayt .
A’s eigvalues and eigvectors converge to K’s eigvalues and modes.

Assumption (Dataset from K-invariant subspace [Budišić+ ’12])
Time-series data (y0 , . . . , ym ) are generated by∀t, yt = g(xt ) whereg = [g1 · · · gn ]T ,and {g1 , . . . , gn } spans a subspace that is invariant to K, i.e.,∃G ⊂ G s.t. ∀g ∈ G, Kg ∈ G andspan{g1 , . . . , gn } = G．

/ Of course, this assumption is not satisfied generally.
5 / 11

Learning Koopman Invariant
Subspaces from DataTo compute KMD, we need data from K-invariant subspace!

• “Data from K-invariant subspace” is not trivial /• Previous approaches:

forget it when data is high-dimensional (e.g. CFD)
transform data by nonlinear basis functions [Williams+ ’15]
I define KMD for observables in RKHS [Kawahara ’16]
II

• Our approach: Learn a K-invariant subspace using data.

6 / 11

Solution: Idea
Theorem (K-invariant subspace)
A set of observables {g1 , . . . , gn } spans a K-invariant subspace if andonly if g = [g1 · · · gn ]T and g ◦ f are linearly dependent.
• Main issue: Learn g that makes g and g ◦ f linearly dependent.
→ Minimize residual sum of squares of linear LS model:
LRSS (g; x0:m ) = kY1 − (Y1 Y0† )Y0 k2F ,Y0 = [g(x0 ) · · · g(xm−1 )],Y1 = [g(x1 ) · · · g(xm )]• And minor modifications to:I

Estimate xt from yt−k+1:t (delay-coordinate embedding [Takens ’81]).
• because y is often rank-deficient

I

Prevent trivial g by adding a term to recover y from the values of g.
7 / 11

Solution: Implementation• The loss function for learning K-invariant subspace:
L(φ, g, h; y) = L̃RSS (φ, g; y) + α Lrec (g, h; y)|{z}P2t kh(gt )−yt k2• Modeling with multilayer perceptrons for each of
φ: estimates xt from yt−k+1:t (delay-coordinate embedder)g :spans K-invariant subspace
I h: recovers y from values of g (to prevent trivial solution)
IIx̃tgg(x̃t ). . . , yt k+1 , yt k+2 , . . . , yt , yt+1 , . . .
original time-series

hLrec

yt

h

Lrec

yt+1LRSSx̃t+1gg(x̃t+1 )8 / 11Experiment example• Generate data from a toy system (λ = 0.9, µ = 0.5):(
λx1,t ,xt+1 = f (x) =µx2,t + (λ2 − µ)x21,tK-invariant subspace of this system is span{x1 , x2 , x21 }, and thecorresponding eigenvalues are λ, µ, λ2 (and λi µj ).

I• Want to estimate the Koopman eigenvalues;
Proposed method (LKIS) successes even with noise in data.
Nonlinear basis function (using {x21 }) fails with noise.

II

0.3

0.1

0.1

00-0.1

-0.1

-0.2
-0.6

-0.4

-0.2

00.2

Re(6)

0.4

0.6

0.8

1

LKIS
linear Hankel
basis exp.
truth

w/ noise

0.2

Im(6)

Im(6)

0.3

LKIS
linear Hankel
basis exp.
truth

w/o noise

0.2-0.2
-0.6

-0.4

-0.2

00.2

0.4

0.60.8

1Re(6)

9 / 11

Application example: unstable phenomena detection• The Koopman eigenfunction with small |λ| corresponds to a
rapidly-decaying component.
I

Watching such eigenfunction, we can detect unstable phenomena.

• Example: laser pulsation data [Santa Fe Time-Series Dataset A]
Plotting learned eigfun. with small |λ|, we see the peaks arecorresponding to the rapid change of amplitude.
I Change-point detection algorithms output similar results.
I20

raw

15
105
0-5-10-15

30-step prediction
truth

LKIS-20105OC-SVM

0-5

10

eft plot shows RMS errors

RuLSIF

Figure 7: The top plot shows the raw time-series

10 / 11

Conclusion

SummaryKoopman analysis• lifts analysis of nonlinear dynamical systems
to linear regime by defining Koopman operator.
• Benefit: modal decomposition, control, etc.
Dynamic mode decomposition• can approximate KMD if data is generated withobservables that span K-inv. subspace.
In this work, we learn K-inv. subspace from data
• RSS minimization with neural networks
Will be presenting at Poster D1-1 tomorrow!
preprint: https://arxiv.org/abs/1710.04340
implementation: https://github.com/thetak11/learning-kis

11 / 11