Advanced Search

Query:

Fill in the form and click »Search«...

Format:

Display: entries per page entries

Zbl 1103.60069
Nadler, Boaz; Lafon, Stéphane; Coifman, Ronald R.; Kevrekidis, Ioannis G.
Diffusion maps, spectral clustering and reaction coordinates of dynamical systems. (English)
[J] Appl. Comput. Harmon. Anal. 21, No. 1, 113-127 (2006). ISSN 1063-5203

Summary: A central problem in data analysis is the low-dimensional representation of high-dimensional data and the concise description of its underlying geometry and density. In the analysis of large scale simulations of complex dynamical systems, where the notion of time evolution comes into play, important problems are the identification of slow variables and dynamically meaningful reaction coordinates that capture the long time evolution of the system. We provide a unifying view of these apparently different tasks, by considering a family of diffusion maps, defined as the embedding of complex (high-dimensional) data onto a low-dimensional Euclidean space, via the eigenvectors of suitably defined random walks defined on the given data sets. Assuming that the data is randomly sampled from an underlying general probability distribution $p(x)=e^{ - U(\bold x)}$, we show that as the number of samples goes to infinity, the eigenvectors of each diffusion map converge to the eigenfunctions of a corresponding differential operator defined on the support of the probability distribution. Different normalizations of the Markov chain on the graph lead to different limiting differential operators. Specifically, the normalized graph Laplacian leads to a backward Fokker-Planck operator with an underlying potential of $2U(\bold x)$, best suited for spectral clustering. A different anisotropic normalization of the random walk leads to the backward Fokker-Planck operator with the potential $U(\bold x)$, best suited for the analysis of the long time asymptotics of high-dimensional stochastic systems governed by a stochastic differential equation with the same potential $U(\bold x)$. Finally, yet another normalization leads to the eigenfunctions of the Laplace-Beltrami (heat) operator on the manifold in which the data resides, best suited for the analysis of the geometry of the data set regardless of its possibly nonuniform density.

MSC 2000:: *60J60 Diffusion processes
60J70 Appl. of diffusion theory
62H30 Statistical classification, etc.

Keywords: random walks; limiting differential operators; backward Fokker-Planck operator; high-dimensional stochastic systems

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]