Fall 2014

Random Walks on Simplicial Complexes and Isoperimetric Inequalities

Wednesday, October 29th, 2014 12:00 pm12:45 pm

Add to Calendar


Calvin Lab Auditorium

The graph Laplacian has been of interest in statistics, machine learning, and theoretical computer science in areas from manifold learning to analysis of Markov chains. A common uses of the graph Laplacian has been in spectral clustering and dimension reduction. A theoretical motivation for why spectral clustering works is the Cheeger inequality which relates the eigenvalues of the graph Laplacian to how disconnected the graph is. We ask how the Cheeger inequality extends to higher-order Laplacians, operators on simplicial complexes, and what clustering means for these higher-order operators. Related to the graph Laplacian is the idea of random walks on graphs. We will define a random walk on simplicial complexes with a stationary distribution that is related to the k-dimensional Laplacian. The stationary distribution reveals (co)homology of the geometry of the random walk. We apply this random walk to the problem of semi-supervised learning, given some labeled observations and many unlabeled observations how does one propagate the labels.