From Trajectories to the Ergodic Partition - An Algorithm

Marko Budišic (Presenter) [e-mail] Dr. Igor Mezic [e-mail]

Description

From Trajectories to the Ergodic PartitionAn AlgorithmMarko Budisic (presenter)[e-mail]. Igor [e-mail] of California, Santa BarbaraDynamics Days, Jan 3{6, 2008Knoxville, TNApproved for Public Release, Distribution Unlimited,DARPA, 02/11/2008Motivation and purposeTrajectory plot Approx. of ergodic partitionλ = 0.3; R = 100; N = 5000 101980.7576)0.5540.25320 10 0.25 0.5 0.75 1θi(mod1)Target GoalMeasure-preserving map on a Quick, coarse partition of phase nite/periodic domain. space.Approved for Public Release, Distribution Unlimited,DARPA, 02/11/2008J (mod1)i15 min talk in one slideCore idea How can we do it?Ergodic subsets { dynamical "Concatenate" trajectories usingatoms in phase space. data clustering methods.Why do we care? Does our solution measure up?Analysis { mapping out Yes.phase space Fast ( minutes) two-stepalgorithm.Design { easier toPartition corresponds to dynamics inexploit naturalknown problems.dynamics ofsystemApproved for Public Release, Distribution Unlimited,DARPA, 02/11/2008Theoretical frameworkBirkho ’s ergodic theoremFor system T :M!M, ifXM is an ergodic subset, then for18x2X;8f2 L (M)temporal averagespatial averagez }| {z }| {Z n h iX1 k f = f (x)d(x) = lim f T (x) = f (x);n!1 nk=0XLevel sets of f ! invariant Grouping criterionpartitionPf 1f (x) = f (y);8f2 LErgodic partition +WP := P1E ff2L x; y2XApproved for Public ...

Informations

• Publié par: Unfo
• Nombre de lectures: 13
• Langue: English

Extrait

dforroveAppiD,esaeleRcilbuPmiliUnontiburist8002

Dynamics Days, Jan 3–6, 2008 Knoxville, TN

University of California, Santa Barbara

MarkoBudisˇic´(presenter) [e-mail] Dr.IgorMezic´ [e-mail]

From

Trajectories to the Ergodic Partition An Algorithm

d,teRPDA02A,1//1

ted,limiA,02DARP02801//1

Trajectory plot

Approx. of ergodic partition

⇒

Motivation and purpose

Goal Quick, coarse partition of phase space.

Target Measure-preserving map on a finite/periodic domain.

veroppAonUnbutistrie,DielsacieRuPlbfdro

ed,DimitnUnlutiortbiD,siaeesRcleliubrPfoedovprAp

Why do we care? Analysis – mapping out phase space Design – easier to exploit natural dynamics of system

Does our solution measure up? Yes. Fast ( ∼ minutes) two-step algorithm. Partition corresponds to dynamics in known problems.

15 min talk in one slide

Core idea Ergodic subsets – dynamical atoms in phase space.

How can we do it? ”Concatenate” trajectories using data clustering methods.

2/11800APRA/20,

lbuProfdevorppAet,dilimnonUubitstrie,DileasicRe

Level sets of f ∗ → invariant partition P f Ergodic partition P E := W f ∈ L 1 µ P f

Grouping criterion f ∗ ( x ) = f ∗ ( y ) , ∀ f ∈ L µ 1 ⇓ x , y ∈ X

Theoretical framework

Birkhoff’s ergodic theorem For system T : M → M , if X ⊂ M is an ergodic subset , then for ∀ x ∈ X , ∀ f ∈ L 1 µ ( M )

ral average z spatial } a | verage { z tempo }| { li 1 n f = Z f ( x ) d µ ( x ) = n → m ∞ n X f h T k ( x ) i = f ∗ ( x ) , X k =0

PRAD20,A/11/8002

Die,ristReicaslerofdlbuPppAevor2008/11/A,02DARPet,dilimnonUubit

Algorithm: 1 Choose a good basis for observables, 2 Pick a large number of ICs in phase space, 3 Simulate system from each IC for an infinite time, 4 Compute time averages of observables along trajectories, 5 Group trajectories with same time averages into sets.

Limitations: No basis in general for L 1 µ ( M ), countably infinite for L 2 µ ( M ), Only finite density of ICs can be chosen, Only finite time evolution is computable.

Result: Implementation of grouping criterion unclear.

On a conceptual level

evorppAasleReicblPuordfnonUubittsir,eiDA,02DARPted,limi2008/11/

Purpose

Periodic

Haar

basis

Implementation

Step 1/2: Simulation

Associate time average vector v i with every trajectory.

PR,A,dADimetnUil

Step 2/2: Clustering

CC Clustering: reveals and labels dominant features

Dominant eigenspace of random walk: natural coordinate system

Euclidean graph: nodes → trajectories edges → g ij = || v i − v j || 2 Diffusion distance graph: adds robustness to data distribution

08

Implementation

1/2002/1eleRcilbuProfdevontiburistDie,as

1

2

3

4

Purpose Implement grouping criterion – assign the same label to similar trajectories.

Appor

ampaddrStan stemstsyTe ofdebuPrRcilaele,DsetrisutibnUiolnmitideD,RAAP0,2/11/2008

Poincare´mapofperiodicallyforced harmonic oscillator Measure-preserving; resonant and chaotic zones λ ∈ (0 , 1) tunes amount of chaos Observables – Haar basis on S 2

Unnecessary detail in chaotic region. No obvious way of color-coding regions.

Description

J n +1 = J n + λ sin(2 πθ n ) θ n +1 = J n +1 + θ n f : S 2 → R n

(mod 1) (mod 1) f ∈ L 2 ( S 2 )

Trajectory plot

rpvopA

AR,D,0PAimnledit

Averaging horizon length

Partition quality analysis

8

Iterations (clockwise): 50, 600, 1700 More iterations: Longer simulation step High spectral ridge (gap)

λ = 0 . 3; 100[ Box / Dim ]

11/2002/elealicRrPubedfooiUnbitusirtesD,vorppA

prAptimilnUnAPRAD,de/2112/,0

λ = 0 . 3; 2000 Iterations

Resolution [ Box / Dim ] (clockwise): 50, 106, 300 Higher resolution: Longer clustering step Low spectral ridge (gap)

Partition quality analysis

Discretization resolution

800ofPrvodeRclebuil,Diseaseutiotrib

rPublicRelease,DpArpvodeof8

λ = 0 . 10

Influence of dynamics ( λ )

2/00

Blue – simulation step Red – total running time

λ = 0 . 75

AR,Dedit112/,0PAtubirtsimilnUnoi innuitgnR mple is Co alysmean scanimfoydixyt