Manifold Learning and Dimensionality Reduction with Diffusion Maps

• This page provides my results of the seminar Learning with Graphs.
• The paper of my presentation was R.R. Coifman, S. Lafon, “Diffusion maps”, Applied and Computational Harmonic Analysis: Special issue on Diffusion Maps and Wavelets, Vol 21, July 2006, pp 5-30.
• Report: DiffusionMapsSeminarReport_RichardSocher.pdf (3MB)
• Slides: DiffusionMaps_RichardSocher.pdf (3MB)
• Code: http://www.ml.uni-saarland.de/GraphDemo/GraphDemo.html is modified by the code snippets in the report.
  • Abstract: This report gives an introduction to diffusion maps, some of their underlying theory, as well as their applications in spectral clustering. First, the shortcomings of linear methods such as PCA are shown to motivate the use of graph-based methods. We then explain Locally Linear Embedding, Isomap and Laplacian eigenmaps, before we give details on diffusion maps and anisotropic diffusion processes.
  • Table of Contents:

1. Introduction
   1. Principal Component Analysis
   2. Graph-Based Algorithms
   3. Locally Linear Embedding
   4. Isomap
   5. Laplacian Eigenmaps
      1. Graph Laplacians
      2. The Algorithm
      3. Algorithm Justification
      4. Eigenmaps - Conclusion
2. Diffusion Maps
   1. Intuition
   2. Diffusion Distance
   3. Embedding
   4. Conclusion
3. Anisotropic Diffusion
   1. Family of Anisotropic Diffusions
   2. Laplace-Beltrami Operator
   3. Influence of Density and Geometry
4. Conclusion
5. Appendix:
   1. PCA code and mapping to Eigenvector
   2. Rayleigh Ritz Proof
   3. Implementation of Laplacian Eigenmaps
   4. Implementation of Anisotropic Diffusion
   5. Implementation of Eigenfunctions for Symmetric and Random Walk Laplacian