Diffusion maps, spectral clustering and reaction coordinates of dynamical systems
By Boaz Nadler, Stéphane Lafon, Ronald R. Coifman, Ioannis G. Kevrekidis. 2005
1,078 citations recorded by the source corpus.
Abstract 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. In this paper 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 datasets. Assuming that the data is randomly sampled from an underlying general probability distribution p ( x ) = e − U ( 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 2 U ( 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 ( 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 ( 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 dataset regardless of its possibly non-uniform density.
Subfields: Computational Theory and Mathematics, Condensed Matter Physics, Mathematical Physics, Representation & Self-Supervised Learning, Numerical Methods & Scientific Computing
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computational Theory and Mathematics
- Amit Singer
- Stéphane Lafon
- Ronald R. Coifman
- Steven L. Brunton
- J. Nathan Kutz
- Ann B. Lee
- Stanley J. Osher
- Guy Gilboa
In Condensed Matter Physics
- Stanley J. Osher
- Guy Gilboa
- Ronald R. Coifman
- Amit Singer
- Stéphane Lafon
- T. Sauer
- Tyrus Berry
- Ann B. Lee
In Mathematical Physics
- Stanley J. Osher
- Guy Gilboa
- Stéphane Lafon
- Ann B. Lee
- Ronald R. Coifman
- Amit Singer
- T. Sauer
- Tyrus Berry
In Representation & Self-Supervised Learning
- Antonio Torralba
- Rob Fergus
- Herv'e J'egou
- Yoshua Bengio
- L. V. D. van der Maaten
- Matthijs Douze
- Amit Singer
- Bharath Hariharan
In Numerical Methods & Scientific Computing
- Steven L. Brunton
- Stanley J. Osher
- Guy Gilboa
- J. Nathan Kutz
- Ronald R. Coifman
- Stéphane Lafon
- Amit Singer
- Ann B. Lee
Citations in the corpus
- Community detection in graphs (2009, neutral): “B) and in a recent analysis by Nadler et al. (Nadler et al., 2006), one defined a dissimilarity measure called “diffusion distance”, which is derived from the probability that the walker visits the target after a fixed number of steps.”
- Dimensionality Reduction: A Comparative Review (2008, background): “Diffusion maps The diffusion maps (DM) framework [68,78] originates from the field of dynamical systems.”
- Local Kernels and the Geometric Structure of Data (2014, positive): “In rough analogy to the principal components from a singular value decomposition, the components of a diffusion map [6, 8] are eigenvectors of a transition matrix for a random walk on the data set.”
- Nonlinear Laplacian spectral analysis for time series with intermittency and low-frequency variability (2012, methodology): “Aij 1⁄4 hAðφjÞ;eii 1⁄4 Z dμðXtÞφjðXtÞXt; [7]”