Diffusion maps, spectral clustering and eigenfunctions of Fokker-Planck operators

Boaz Nadler, Stéphane Lafon, Ronald R. Coifman, Ioannis G. Kevrekidis

Research output: Chapter in Book/Report/Conference proceedingConference contribution

253 Scopus citations

Abstract

This paper presents a diffusion based probabilistic interpretation of spectral clustering and dimensionality reduction algorithms that use the eigenvectors of the normalized graph Laplacian. Given the pairwise adjacencymatrix of all points, we define a diffusion distance between any two data points and show that the low dimensional representation of the data by the first few eigenvectors of the corresponding Markov matrix is optimal under a certain mean squared error criterion. Furthermore, assuming that data points are random samples from a density p(x) = e -U(x) we identify these eigenvectors as discrete approximations of eigenfunctions of a Fokker-Planck operator in a potential 2U(x) with reflecting boundary conditions. Finally, applying known results regarding the eigenvalues and eigenfunctions of the continuous Fokker-Planck operator, we provide a mathematical justification for the success of spectral clustering and dimensional reduction algorithms based on these first few eigenvectors. This analysis elucidates, in terms of the characteristics of diffusion processes, many empirical findings regarding spectral clustering algorithms.

Original languageEnglish (US)
Title of host publicationAdvances in Neural Information Processing Systems 18 - Proceedings of the 2005 Conference
Pages955-962
Number of pages8
StatePublished - Dec 1 2005
Event2005 Annual Conference on Neural Information Processing Systems, NIPS 2005 - Vancouver, BC, Canada
Duration: Dec 5 2005Dec 8 2005

Publication series

NameAdvances in Neural Information Processing Systems
ISSN (Print)1049-5258

Other

Other2005 Annual Conference on Neural Information Processing Systems, NIPS 2005
CountryCanada
CityVancouver, BC
Period12/5/0512/8/05

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Information Systems
  • Signal Processing

Keywords

  • Algorithms and architectures
  • Learning theory

Fingerprint Dive into the research topics of 'Diffusion maps, spectral clustering and eigenfunctions of Fokker-Planck operators'. Together they form a unique fingerprint.

Cite this