Wesley Hamilton – Part 2: Optimal Transport and Discrete/Continuum Laplacians – Advanced GMA Seminar

Title:  Optimal Transport and Discrete/Continuum Laplacians

Abstract:  In the past 20 years, spectral methods have shown to be increasingly effective at a wide variety of data analytic problems. These spectral methods usually involve a graph Laplacian constructed from the data points, which behaves like a discrete version of the familiar (second order differential operator) continuum Laplacian. Since we’re primarily interested in the spectrum of the graph Laplacian, a natural question is: if we take a denser and denser sampling, does the spectrum of the graph Laplacian converge to the spectrum of the continuum Laplacian? In this series of lectures, we’ll see that we do indeed have convergence of the spectrum from the discrete to continuum setting. Moreover, we’ll see that the graph Laplacian’s eigenvectors also converge (in an appropriate sense) to the continuum Laplacian’s eigenfunctions: the fact that discrete eigenstuff converges to the corresponding continuum eigenstuff is what we call consistency. Lecture 1 will provide an overview of the types of consistency problems that arise and have been studied, as well as some applications. In lecture 2, we’ll focus on pointwise convergence results, including an analysis of the classic Laplacian Eigenmap algorithm and its related constructions. Lecture 3 (and onwards) will take a variational point of view, using an optimal transport framework to get similar convergence results. This new framework will also let us determine the consistency of other graph operators, such as the graph cut converging to arclength, and the graph total variation converging to Dirichlet energy.