Cheeger Cuts and p-Spectral Clustering
published: July 30, 2009, recorded: June 2009, views: 5621
Report a problem or upload filesIf you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
Spectral clustering has become in recent years one of the most popular clustering algorithm. In this talk I discuss a generalized version of spectral clustering based on the second eigenvector of the graph p-Laplacian, a non-linear generalization of the graph Laplacian. The clustering obtained for 1<=2 can be seen as an interpolation of the relaxation of the normalized cut (p=2) and the Cheeger cut (p=1). However, the main motivation for p-spectral clustering is the fact, that one can show that the cut value obtained by thresholding the second eigenvector of the p-Laplacian converges towards the optimal Cheeger cut as p tends to 1. I will also present an efficient implementation which allows to do p-spectral clustering for large scale datasets.
Link this pageWould you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !