La lecture en ligne est gratuite
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres
Télécharger Lire

From Trajectories to the Ergodic Partition - An Algorithm

De
14 pages
From Trajectories to the Ergodic PartitionAn AlgorithmMarko Budisic (presenter)mbudisic@engineering.ucsb.eduDr. Igor Mezicmezic@engineering.ucsb.eduUniversity 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 ...
Voir plus Voir moins
dforroveAppiD,esaeleRcilbuPmiliUnontiburist8002
Dynamics Days, Jan 3–6, 2008 Knoxville, TN
University of California, Santa Barbara
MarkoBudisˇic´(presenter) mbudisic@engineering.ucsb.edu Dr.IgorMezic´ mezic@engineering.ucsb.edu
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
ampaddrStanstemstsyTeofdebuPrRcilaele,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/,0PAtubirtsimilnUnoiinnuitgnRmpleisCoalysmeanscanimfoydixyt
Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin